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