| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright 2014 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 <set> | |
| 6 | |
| 7 #include "src/v8.h" | |
| 8 | |
| 9 #include "graph-tester.h" | |
| 10 #include "src/compiler/graph-reducer.h" | |
| 11 #include "src/compiler/node.h" | |
| 12 #include "src/compiler/operator.h" | |
| 13 | |
| 14 using namespace v8::internal; | |
| 15 using namespace v8::internal::compiler; | |
| 16 | |
| 17 const uint8_t OPCODE_A0 = 10; | |
| 18 const uint8_t OPCODE_A1 = 11; | |
| 19 const uint8_t OPCODE_A2 = 12; | |
| 20 const uint8_t OPCODE_B0 = 20; | |
| 21 const uint8_t OPCODE_B1 = 21; | |
| 22 const uint8_t OPCODE_B2 = 22; | |
| 23 const uint8_t OPCODE_C0 = 30; | |
| 24 const uint8_t OPCODE_C1 = 31; | |
| 25 const uint8_t OPCODE_C2 = 32; | |
| 26 | |
| 27 static Operator OPA0(OPCODE_A0, Operator::kNoWrite, "opa0", 0, 0, 0, 0, 0, 0); | |
| 28 static Operator OPA1(OPCODE_A1, Operator::kNoWrite, "opa1", 1, 0, 0, 0, 0, 0); | |
| 29 static Operator OPA2(OPCODE_A2, Operator::kNoWrite, "opa2", 2, 0, 0, 0, 0, 0); | |
| 30 static Operator OPB0(OPCODE_B0, Operator::kNoWrite, "opa0", 0, 0, 0, 0, 0, 0); | |
| 31 static Operator OPB1(OPCODE_B1, Operator::kNoWrite, "opa1", 1, 0, 0, 0, 0, 0); | |
| 32 static Operator OPB2(OPCODE_B2, Operator::kNoWrite, "opa2", 2, 0, 0, 0, 0, 0); | |
| 33 static Operator OPC0(OPCODE_C0, Operator::kNoWrite, "opc0", 0, 0, 0, 0, 0, 0); | |
| 34 static Operator OPC1(OPCODE_C1, Operator::kNoWrite, "opc1", 1, 0, 0, 0, 0, 0); | |
| 35 static Operator OPC2(OPCODE_C2, Operator::kNoWrite, "opc2", 2, 0, 0, 0, 0, 0); | |
| 36 | |
| 37 | |
| 38 // Replaces all "A" operators with "B" operators without creating new nodes. | |
| 39 class InPlaceABReducer : public Reducer { | |
| 40 public: | |
| 41 virtual Reduction Reduce(Node* node) { | |
| 42 switch (node->op()->opcode()) { | |
| 43 case OPCODE_A0: | |
| 44 CHECK_EQ(0, node->InputCount()); | |
| 45 node->set_op(&OPB0); | |
| 46 return Replace(node); | |
| 47 case OPCODE_A1: | |
| 48 CHECK_EQ(1, node->InputCount()); | |
| 49 node->set_op(&OPB1); | |
| 50 return Replace(node); | |
| 51 case OPCODE_A2: | |
| 52 CHECK_EQ(2, node->InputCount()); | |
| 53 node->set_op(&OPB2); | |
| 54 return Replace(node); | |
| 55 } | |
| 56 return NoChange(); | |
| 57 } | |
| 58 }; | |
| 59 | |
| 60 | |
| 61 // Replaces all "A" operators with "B" operators by allocating new nodes. | |
| 62 class NewABReducer : public Reducer { | |
| 63 public: | |
| 64 explicit NewABReducer(Graph* graph) : graph_(graph) {} | |
| 65 virtual Reduction Reduce(Node* node) { | |
| 66 switch (node->op()->opcode()) { | |
| 67 case OPCODE_A0: | |
| 68 CHECK_EQ(0, node->InputCount()); | |
| 69 return Replace(graph_->NewNode(&OPB0)); | |
| 70 case OPCODE_A1: | |
| 71 CHECK_EQ(1, node->InputCount()); | |
| 72 return Replace(graph_->NewNode(&OPB1, node->InputAt(0))); | |
| 73 case OPCODE_A2: | |
| 74 CHECK_EQ(2, node->InputCount()); | |
| 75 return Replace( | |
| 76 graph_->NewNode(&OPB2, node->InputAt(0), node->InputAt(1))); | |
| 77 } | |
| 78 return NoChange(); | |
| 79 } | |
| 80 Graph* graph_; | |
| 81 }; | |
| 82 | |
| 83 | |
| 84 // Replaces all "B" operators with "C" operators without creating new nodes. | |
| 85 class InPlaceBCReducer : public Reducer { | |
| 86 public: | |
| 87 virtual Reduction Reduce(Node* node) { | |
| 88 switch (node->op()->opcode()) { | |
| 89 case OPCODE_B0: | |
| 90 CHECK_EQ(0, node->InputCount()); | |
| 91 node->set_op(&OPC0); | |
| 92 return Replace(node); | |
| 93 case OPCODE_B1: | |
| 94 CHECK_EQ(1, node->InputCount()); | |
| 95 node->set_op(&OPC1); | |
| 96 return Replace(node); | |
| 97 case OPCODE_B2: | |
| 98 CHECK_EQ(2, node->InputCount()); | |
| 99 node->set_op(&OPC2); | |
| 100 return Replace(node); | |
| 101 } | |
| 102 return NoChange(); | |
| 103 } | |
| 104 }; | |
| 105 | |
| 106 | |
| 107 // Wraps all "OPA0" nodes in "OPB1" operators by allocating new nodes. | |
| 108 class A0Wrapper FINAL : public Reducer { | |
| 109 public: | |
| 110 explicit A0Wrapper(Graph* graph) : graph_(graph) {} | |
| 111 virtual Reduction Reduce(Node* node) OVERRIDE { | |
| 112 switch (node->op()->opcode()) { | |
| 113 case OPCODE_A0: | |
| 114 CHECK_EQ(0, node->InputCount()); | |
| 115 return Replace(graph_->NewNode(&OPB1, node)); | |
| 116 } | |
| 117 return NoChange(); | |
| 118 } | |
| 119 Graph* graph_; | |
| 120 }; | |
| 121 | |
| 122 | |
| 123 // Wraps all "OPB0" nodes in two "OPC1" operators by allocating new nodes. | |
| 124 class B0Wrapper FINAL : public Reducer { | |
| 125 public: | |
| 126 explicit B0Wrapper(Graph* graph) : graph_(graph) {} | |
| 127 virtual Reduction Reduce(Node* node) OVERRIDE { | |
| 128 switch (node->op()->opcode()) { | |
| 129 case OPCODE_B0: | |
| 130 CHECK_EQ(0, node->InputCount()); | |
| 131 return Replace(graph_->NewNode(&OPC1, graph_->NewNode(&OPC1, node))); | |
| 132 } | |
| 133 return NoChange(); | |
| 134 } | |
| 135 Graph* graph_; | |
| 136 }; | |
| 137 | |
| 138 | |
| 139 // Replaces all "OPA1" nodes with the first input. | |
| 140 class A1Forwarder : public Reducer { | |
| 141 virtual Reduction Reduce(Node* node) { | |
| 142 switch (node->op()->opcode()) { | |
| 143 case OPCODE_A1: | |
| 144 CHECK_EQ(1, node->InputCount()); | |
| 145 return Replace(node->InputAt(0)); | |
| 146 } | |
| 147 return NoChange(); | |
| 148 } | |
| 149 }; | |
| 150 | |
| 151 | |
| 152 // Replaces all "OPB1" nodes with the first input. | |
| 153 class B1Forwarder : public Reducer { | |
| 154 virtual Reduction Reduce(Node* node) { | |
| 155 switch (node->op()->opcode()) { | |
| 156 case OPCODE_B1: | |
| 157 CHECK_EQ(1, node->InputCount()); | |
| 158 return Replace(node->InputAt(0)); | |
| 159 } | |
| 160 return NoChange(); | |
| 161 } | |
| 162 }; | |
| 163 | |
| 164 | |
| 165 // Swaps the inputs to "OP2A" and "OP2B" nodes based on ids. | |
| 166 class AB2Sorter : public Reducer { | |
| 167 virtual Reduction Reduce(Node* node) { | |
| 168 switch (node->op()->opcode()) { | |
| 169 case OPCODE_A2: | |
| 170 case OPCODE_B2: | |
| 171 CHECK_EQ(2, node->InputCount()); | |
| 172 Node* x = node->InputAt(0); | |
| 173 Node* y = node->InputAt(1); | |
| 174 if (x->id() > y->id()) { | |
| 175 node->ReplaceInput(0, y); | |
| 176 node->ReplaceInput(1, x); | |
| 177 return Replace(node); | |
| 178 } | |
| 179 } | |
| 180 return NoChange(); | |
| 181 } | |
| 182 }; | |
| 183 | |
| 184 | |
| 185 // Simply records the nodes visited. | |
| 186 class ReducerRecorder : public Reducer { | |
| 187 public: | |
| 188 typedef std::set<Node*, std::less<Node*>, zone_allocator<Node*>> NodeSet; | |
| 189 explicit ReducerRecorder(Zone* zone) | |
| 190 : set(NodeSet::key_compare(), NodeSet::allocator_type(zone)) {} | |
| 191 virtual Reduction Reduce(Node* node) { | |
| 192 set.insert(node); | |
| 193 return NoChange(); | |
| 194 } | |
| 195 void CheckContains(Node* node) { | |
| 196 CHECK_EQ(1, static_cast<int>(set.count(node))); | |
| 197 } | |
| 198 NodeSet set; | |
| 199 }; | |
| 200 | |
| 201 | |
| 202 TEST(ReduceGraphFromEnd1) { | |
| 203 GraphTester graph; | |
| 204 | |
| 205 Node* n1 = graph.NewNode(&OPA0); | |
| 206 Node* end = graph.NewNode(&OPA1, n1); | |
| 207 graph.SetEnd(end); | |
| 208 | |
| 209 GraphReducer reducer(&graph, graph.zone()); | |
| 210 ReducerRecorder recorder(graph.zone()); | |
| 211 reducer.AddReducer(&recorder); | |
| 212 reducer.ReduceGraph(); | |
| 213 recorder.CheckContains(n1); | |
| 214 recorder.CheckContains(end); | |
| 215 } | |
| 216 | |
| 217 | |
| 218 TEST(ReduceGraphFromEnd2) { | |
| 219 GraphTester graph; | |
| 220 | |
| 221 Node* n1 = graph.NewNode(&OPA0); | |
| 222 Node* n2 = graph.NewNode(&OPA1, n1); | |
| 223 Node* n3 = graph.NewNode(&OPA1, n1); | |
| 224 Node* end = graph.NewNode(&OPA2, n2, n3); | |
| 225 graph.SetEnd(end); | |
| 226 | |
| 227 GraphReducer reducer(&graph, graph.zone()); | |
| 228 ReducerRecorder recorder(graph.zone()); | |
| 229 reducer.AddReducer(&recorder); | |
| 230 reducer.ReduceGraph(); | |
| 231 recorder.CheckContains(n1); | |
| 232 recorder.CheckContains(n2); | |
| 233 recorder.CheckContains(n3); | |
| 234 recorder.CheckContains(end); | |
| 235 } | |
| 236 | |
| 237 | |
| 238 TEST(ReduceInPlace1) { | |
| 239 GraphTester graph; | |
| 240 | |
| 241 Node* n1 = graph.NewNode(&OPA0); | |
| 242 Node* end = graph.NewNode(&OPA1, n1); | |
| 243 graph.SetEnd(end); | |
| 244 | |
| 245 GraphReducer reducer(&graph, graph.zone()); | |
| 246 InPlaceABReducer r; | |
| 247 reducer.AddReducer(&r); | |
| 248 | |
| 249 // Tests A* => B* with in-place updates. | |
| 250 for (int i = 0; i < 3; i++) { | |
| 251 int before = graph.NodeCount(); | |
| 252 reducer.ReduceGraph(); | |
| 253 CHECK_EQ(before, graph.NodeCount()); | |
| 254 CHECK_EQ(&OPB0, n1->op()); | |
| 255 CHECK_EQ(&OPB1, end->op()); | |
| 256 CHECK_EQ(n1, end->InputAt(0)); | |
| 257 } | |
| 258 } | |
| 259 | |
| 260 | |
| 261 TEST(ReduceInPlace2) { | |
| 262 GraphTester graph; | |
| 263 | |
| 264 Node* n1 = graph.NewNode(&OPA0); | |
| 265 Node* n2 = graph.NewNode(&OPA1, n1); | |
| 266 Node* n3 = graph.NewNode(&OPA1, n1); | |
| 267 Node* end = graph.NewNode(&OPA2, n2, n3); | |
| 268 graph.SetEnd(end); | |
| 269 | |
| 270 GraphReducer reducer(&graph, graph.zone()); | |
| 271 InPlaceABReducer r; | |
| 272 reducer.AddReducer(&r); | |
| 273 | |
| 274 // Tests A* => B* with in-place updates. | |
| 275 for (int i = 0; i < 3; i++) { | |
| 276 int before = graph.NodeCount(); | |
| 277 reducer.ReduceGraph(); | |
| 278 CHECK_EQ(before, graph.NodeCount()); | |
| 279 CHECK_EQ(&OPB0, n1->op()); | |
| 280 CHECK_EQ(&OPB1, n2->op()); | |
| 281 CHECK_EQ(n1, n2->InputAt(0)); | |
| 282 CHECK_EQ(&OPB1, n3->op()); | |
| 283 CHECK_EQ(n1, n3->InputAt(0)); | |
| 284 CHECK_EQ(&OPB2, end->op()); | |
| 285 CHECK_EQ(n2, end->InputAt(0)); | |
| 286 CHECK_EQ(n3, end->InputAt(1)); | |
| 287 } | |
| 288 } | |
| 289 | |
| 290 | |
| 291 TEST(ReduceNew1) { | |
| 292 GraphTester graph; | |
| 293 | |
| 294 Node* n1 = graph.NewNode(&OPA0); | |
| 295 Node* n2 = graph.NewNode(&OPA1, n1); | |
| 296 Node* n3 = graph.NewNode(&OPA1, n1); | |
| 297 Node* end = graph.NewNode(&OPA2, n2, n3); | |
| 298 graph.SetEnd(end); | |
| 299 | |
| 300 GraphReducer reducer(&graph, graph.zone()); | |
| 301 NewABReducer r(&graph); | |
| 302 reducer.AddReducer(&r); | |
| 303 | |
| 304 // Tests A* => B* while creating new nodes. | |
| 305 for (int i = 0; i < 3; i++) { | |
| 306 int before = graph.NodeCount(); | |
| 307 reducer.ReduceGraph(); | |
| 308 if (i == 0) { | |
| 309 CHECK_NE(before, graph.NodeCount()); | |
| 310 } else { | |
| 311 CHECK_EQ(before, graph.NodeCount()); | |
| 312 } | |
| 313 Node* nend = graph.end(); | |
| 314 CHECK_NE(end, nend); // end() should be updated too. | |
| 315 | |
| 316 Node* nn2 = nend->InputAt(0); | |
| 317 Node* nn3 = nend->InputAt(1); | |
| 318 Node* nn1 = nn2->InputAt(0); | |
| 319 | |
| 320 CHECK_EQ(nn1, nn3->InputAt(0)); | |
| 321 | |
| 322 CHECK_EQ(&OPB0, nn1->op()); | |
| 323 CHECK_EQ(&OPB1, nn2->op()); | |
| 324 CHECK_EQ(&OPB1, nn3->op()); | |
| 325 CHECK_EQ(&OPB2, nend->op()); | |
| 326 } | |
| 327 } | |
| 328 | |
| 329 | |
| 330 TEST(Wrapping1) { | |
| 331 GraphTester graph; | |
| 332 | |
| 333 Node* end = graph.NewNode(&OPA0); | |
| 334 graph.SetEnd(end); | |
| 335 CHECK_EQ(1, graph.NodeCount()); | |
| 336 | |
| 337 GraphReducer reducer(&graph, graph.zone()); | |
| 338 A0Wrapper r(&graph); | |
| 339 reducer.AddReducer(&r); | |
| 340 | |
| 341 reducer.ReduceGraph(); | |
| 342 CHECK_EQ(2, graph.NodeCount()); | |
| 343 | |
| 344 Node* nend = graph.end(); | |
| 345 CHECK_NE(end, nend); | |
| 346 CHECK_EQ(&OPB1, nend->op()); | |
| 347 CHECK_EQ(1, nend->InputCount()); | |
| 348 CHECK_EQ(end, nend->InputAt(0)); | |
| 349 } | |
| 350 | |
| 351 | |
| 352 TEST(Wrapping2) { | |
| 353 GraphTester graph; | |
| 354 | |
| 355 Node* end = graph.NewNode(&OPB0); | |
| 356 graph.SetEnd(end); | |
| 357 CHECK_EQ(1, graph.NodeCount()); | |
| 358 | |
| 359 GraphReducer reducer(&graph, graph.zone()); | |
| 360 B0Wrapper r(&graph); | |
| 361 reducer.AddReducer(&r); | |
| 362 | |
| 363 reducer.ReduceGraph(); | |
| 364 CHECK_EQ(3, graph.NodeCount()); | |
| 365 | |
| 366 Node* nend = graph.end(); | |
| 367 CHECK_NE(end, nend); | |
| 368 CHECK_EQ(&OPC1, nend->op()); | |
| 369 CHECK_EQ(1, nend->InputCount()); | |
| 370 | |
| 371 Node* n1 = nend->InputAt(0); | |
| 372 CHECK_NE(end, n1); | |
| 373 CHECK_EQ(&OPC1, n1->op()); | |
| 374 CHECK_EQ(1, n1->InputCount()); | |
| 375 CHECK_EQ(end, n1->InputAt(0)); | |
| 376 } | |
| 377 | |
| 378 | |
| 379 TEST(Forwarding1) { | |
| 380 GraphTester graph; | |
| 381 | |
| 382 Node* n1 = graph.NewNode(&OPA0); | |
| 383 Node* end = graph.NewNode(&OPA1, n1); | |
| 384 graph.SetEnd(end); | |
| 385 | |
| 386 GraphReducer reducer(&graph, graph.zone()); | |
| 387 A1Forwarder r; | |
| 388 reducer.AddReducer(&r); | |
| 389 | |
| 390 // Tests A1(x) => x | |
| 391 for (int i = 0; i < 3; i++) { | |
| 392 int before = graph.NodeCount(); | |
| 393 reducer.ReduceGraph(); | |
| 394 CHECK_EQ(before, graph.NodeCount()); | |
| 395 CHECK_EQ(&OPA0, n1->op()); | |
| 396 CHECK_EQ(n1, graph.end()); | |
| 397 } | |
| 398 } | |
| 399 | |
| 400 | |
| 401 TEST(Forwarding2) { | |
| 402 GraphTester graph; | |
| 403 | |
| 404 Node* n1 = graph.NewNode(&OPA0); | |
| 405 Node* n2 = graph.NewNode(&OPA1, n1); | |
| 406 Node* n3 = graph.NewNode(&OPA1, n1); | |
| 407 Node* end = graph.NewNode(&OPA2, n2, n3); | |
| 408 graph.SetEnd(end); | |
| 409 | |
| 410 GraphReducer reducer(&graph, graph.zone()); | |
| 411 A1Forwarder r; | |
| 412 reducer.AddReducer(&r); | |
| 413 | |
| 414 // Tests reducing A2(A1(x), A1(y)) => A2(x, y). | |
| 415 for (int i = 0; i < 3; i++) { | |
| 416 int before = graph.NodeCount(); | |
| 417 reducer.ReduceGraph(); | |
| 418 CHECK_EQ(before, graph.NodeCount()); | |
| 419 CHECK_EQ(&OPA0, n1->op()); | |
| 420 CHECK_EQ(n1, end->InputAt(0)); | |
| 421 CHECK_EQ(n1, end->InputAt(1)); | |
| 422 CHECK_EQ(&OPA2, end->op()); | |
| 423 CHECK_EQ(0, n2->UseCount()); | |
| 424 CHECK_EQ(0, n3->UseCount()); | |
| 425 } | |
| 426 } | |
| 427 | |
| 428 | |
| 429 TEST(Forwarding3) { | |
| 430 // Tests reducing a chain of A1(A1(A1(A1(x)))) => x. | |
| 431 for (int i = 0; i < 8; i++) { | |
| 432 GraphTester graph; | |
| 433 | |
| 434 Node* n1 = graph.NewNode(&OPA0); | |
| 435 Node* end = n1; | |
| 436 for (int j = 0; j < i; j++) { | |
| 437 end = graph.NewNode(&OPA1, end); | |
| 438 } | |
| 439 graph.SetEnd(end); | |
| 440 | |
| 441 GraphReducer reducer(&graph, graph.zone()); | |
| 442 A1Forwarder r; | |
| 443 reducer.AddReducer(&r); | |
| 444 | |
| 445 for (int i = 0; i < 3; i++) { | |
| 446 int before = graph.NodeCount(); | |
| 447 reducer.ReduceGraph(); | |
| 448 CHECK_EQ(before, graph.NodeCount()); | |
| 449 CHECK_EQ(&OPA0, n1->op()); | |
| 450 CHECK_EQ(n1, graph.end()); | |
| 451 } | |
| 452 } | |
| 453 } | |
| 454 | |
| 455 | |
| 456 TEST(ReduceForward1) { | |
| 457 GraphTester graph; | |
| 458 | |
| 459 Node* n1 = graph.NewNode(&OPA0); | |
| 460 Node* n2 = graph.NewNode(&OPA1, n1); | |
| 461 Node* n3 = graph.NewNode(&OPA1, n1); | |
| 462 Node* end = graph.NewNode(&OPA2, n2, n3); | |
| 463 graph.SetEnd(end); | |
| 464 | |
| 465 GraphReducer reducer(&graph, graph.zone()); | |
| 466 InPlaceABReducer r; | |
| 467 B1Forwarder f; | |
| 468 reducer.AddReducer(&r); | |
| 469 reducer.AddReducer(&f); | |
| 470 | |
| 471 // Tests first reducing A => B, then B1(x) => x. | |
| 472 for (int i = 0; i < 3; i++) { | |
| 473 int before = graph.NodeCount(); | |
| 474 reducer.ReduceGraph(); | |
| 475 CHECK_EQ(before, graph.NodeCount()); | |
| 476 CHECK_EQ(&OPB0, n1->op()); | |
| 477 CHECK(n2->IsDead()); | |
| 478 CHECK_EQ(n1, end->InputAt(0)); | |
| 479 CHECK(n3->IsDead()); | |
| 480 CHECK_EQ(n1, end->InputAt(0)); | |
| 481 CHECK_EQ(&OPB2, end->op()); | |
| 482 CHECK_EQ(0, n2->UseCount()); | |
| 483 CHECK_EQ(0, n3->UseCount()); | |
| 484 } | |
| 485 } | |
| 486 | |
| 487 | |
| 488 TEST(Sorter1) { | |
| 489 HandleAndZoneScope scope; | |
| 490 AB2Sorter r; | |
| 491 for (int i = 0; i < 6; i++) { | |
| 492 GraphTester graph; | |
| 493 | |
| 494 Node* n1 = graph.NewNode(&OPA0); | |
| 495 Node* n2 = graph.NewNode(&OPA1, n1); | |
| 496 Node* n3 = graph.NewNode(&OPA1, n1); | |
| 497 Node* end = NULL; // Initialize to please the compiler. | |
| 498 | |
| 499 if (i == 0) end = graph.NewNode(&OPA2, n2, n3); | |
| 500 if (i == 1) end = graph.NewNode(&OPA2, n3, n2); | |
| 501 if (i == 2) end = graph.NewNode(&OPA2, n2, n1); | |
| 502 if (i == 3) end = graph.NewNode(&OPA2, n1, n2); | |
| 503 if (i == 4) end = graph.NewNode(&OPA2, n3, n1); | |
| 504 if (i == 5) end = graph.NewNode(&OPA2, n1, n3); | |
| 505 | |
| 506 graph.SetEnd(end); | |
| 507 | |
| 508 GraphReducer reducer(&graph, graph.zone()); | |
| 509 reducer.AddReducer(&r); | |
| 510 | |
| 511 int before = graph.NodeCount(); | |
| 512 reducer.ReduceGraph(); | |
| 513 CHECK_EQ(before, graph.NodeCount()); | |
| 514 CHECK_EQ(&OPA0, n1->op()); | |
| 515 CHECK_EQ(&OPA1, n2->op()); | |
| 516 CHECK_EQ(&OPA1, n3->op()); | |
| 517 CHECK_EQ(&OPA2, end->op()); | |
| 518 CHECK_EQ(end, graph.end()); | |
| 519 CHECK(end->InputAt(0)->id() <= end->InputAt(1)->id()); | |
| 520 } | |
| 521 } | |
| 522 | |
| 523 | |
| 524 // Generate a node graph with the given permutations. | |
| 525 void GenDAG(Graph* graph, int* p3, int* p2, int* p1) { | |
| 526 Node* level4 = graph->NewNode(&OPA0); | |
| 527 Node* level3[] = {graph->NewNode(&OPA1, level4), | |
| 528 graph->NewNode(&OPA1, level4)}; | |
| 529 | |
| 530 Node* level2[] = {graph->NewNode(&OPA1, level3[p3[0]]), | |
| 531 graph->NewNode(&OPA1, level3[p3[1]]), | |
| 532 graph->NewNode(&OPA1, level3[p3[0]]), | |
| 533 graph->NewNode(&OPA1, level3[p3[1]])}; | |
| 534 | |
| 535 Node* level1[] = {graph->NewNode(&OPA2, level2[p2[0]], level2[p2[1]]), | |
| 536 graph->NewNode(&OPA2, level2[p2[2]], level2[p2[3]])}; | |
| 537 | |
| 538 Node* end = graph->NewNode(&OPA2, level1[p1[0]], level1[p1[1]]); | |
| 539 graph->SetEnd(end); | |
| 540 } | |
| 541 | |
| 542 | |
| 543 TEST(SortForwardReduce) { | |
| 544 GraphTester graph; | |
| 545 | |
| 546 // Tests combined reductions on a series of DAGs. | |
| 547 for (int j = 0; j < 2; j++) { | |
| 548 int p3[] = {j, 1 - j}; | |
| 549 for (int m = 0; m < 2; m++) { | |
| 550 int p1[] = {m, 1 - m}; | |
| 551 for (int k = 0; k < 24; k++) { // All permutations of 0, 1, 2, 3 | |
| 552 int p2[] = {-1, -1, -1, -1}; | |
| 553 int n = k; | |
| 554 for (int d = 4; d >= 1; d--) { // Construct permutation. | |
| 555 int p = n % d; | |
| 556 for (int z = 0; z < 4; z++) { | |
| 557 if (p2[z] == -1) { | |
| 558 if (p == 0) p2[z] = d - 1; | |
| 559 p--; | |
| 560 } | |
| 561 } | |
| 562 n = n / d; | |
| 563 } | |
| 564 | |
| 565 GenDAG(&graph, p3, p2, p1); | |
| 566 | |
| 567 GraphReducer reducer(&graph, graph.zone()); | |
| 568 AB2Sorter r1; | |
| 569 A1Forwarder r2; | |
| 570 InPlaceABReducer r3; | |
| 571 reducer.AddReducer(&r1); | |
| 572 reducer.AddReducer(&r2); | |
| 573 reducer.AddReducer(&r3); | |
| 574 | |
| 575 reducer.ReduceGraph(); | |
| 576 | |
| 577 Node* end = graph.end(); | |
| 578 CHECK_EQ(&OPB2, end->op()); | |
| 579 Node* n1 = end->InputAt(0); | |
| 580 Node* n2 = end->InputAt(1); | |
| 581 CHECK_NE(n1, n2); | |
| 582 CHECK(n1->id() < n2->id()); | |
| 583 CHECK_EQ(&OPB2, n1->op()); | |
| 584 CHECK_EQ(&OPB2, n2->op()); | |
| 585 Node* n4 = n1->InputAt(0); | |
| 586 CHECK_EQ(&OPB0, n4->op()); | |
| 587 CHECK_EQ(n4, n1->InputAt(1)); | |
| 588 CHECK_EQ(n4, n2->InputAt(0)); | |
| 589 CHECK_EQ(n4, n2->InputAt(1)); | |
| 590 } | |
| 591 } | |
| 592 } | |
| 593 } | |
| 594 | |
| 595 | |
| 596 TEST(Order) { | |
| 597 // Test that the order of reducers doesn't matter, as they should be | |
| 598 // rerun for changed nodes. | |
| 599 for (int i = 0; i < 2; i++) { | |
| 600 GraphTester graph; | |
| 601 | |
| 602 Node* n1 = graph.NewNode(&OPA0); | |
| 603 Node* end = graph.NewNode(&OPA1, n1); | |
| 604 graph.SetEnd(end); | |
| 605 | |
| 606 GraphReducer reducer(&graph, graph.zone()); | |
| 607 InPlaceABReducer abr; | |
| 608 InPlaceBCReducer bcr; | |
| 609 if (i == 0) { | |
| 610 reducer.AddReducer(&abr); | |
| 611 reducer.AddReducer(&bcr); | |
| 612 } else { | |
| 613 reducer.AddReducer(&bcr); | |
| 614 reducer.AddReducer(&abr); | |
| 615 } | |
| 616 | |
| 617 // Tests A* => C* with in-place updates. | |
| 618 for (int i = 0; i < 3; i++) { | |
| 619 int before = graph.NodeCount(); | |
| 620 reducer.ReduceGraph(); | |
| 621 CHECK_EQ(before, graph.NodeCount()); | |
| 622 CHECK_EQ(&OPC0, n1->op()); | |
| 623 CHECK_EQ(&OPC1, end->op()); | |
| 624 CHECK_EQ(n1, end->InputAt(0)); | |
| 625 } | |
| 626 } | |
| 627 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 867583002:
Convert compiler cctest to unit tests, part 1 (Closed)
Base URL: https://chromium.googlesource.com/v8/v8.git@master