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.
7 #include "graph-tester.h"
8 #include "src/compiler/generic-node-inl.h"
9 #include "src/compiler/graph-reducer.h"
11 using namespace v8::internal;
12 using namespace v8::internal::compiler;
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;
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");
35 // Replaces all "A" operators with "B" operators without creating new nodes.
36 class InPlaceABReducer : public Reducer {
38 virtual Reduction Reduce(Node* node) {
39 switch (node->op()->opcode()) {
41 CHECK_EQ(0, node->InputCount());
45 CHECK_EQ(1, node->InputCount());
49 CHECK_EQ(2, node->InputCount());
58 // Replaces all "A" operators with "B" operators by allocating new nodes.
59 class NewABReducer : public Reducer {
61 explicit NewABReducer(Graph* graph) : graph_(graph) {}
62 virtual Reduction Reduce(Node* node) {
63 switch (node->op()->opcode()) {
65 CHECK_EQ(0, node->InputCount());
66 return Replace(graph_->NewNode(&OPB0));
68 CHECK_EQ(1, node->InputCount());
69 return Replace(graph_->NewNode(&OPB1, node->InputAt(0)));
71 CHECK_EQ(2, node->InputCount());
73 graph_->NewNode(&OPB2, node->InputAt(0), node->InputAt(1)));
81 // Replaces all "B" operators with "C" operators without creating new nodes.
82 class InPlaceBCReducer : public Reducer {
84 virtual Reduction Reduce(Node* node) {
85 switch (node->op()->opcode()) {
87 CHECK_EQ(0, node->InputCount());
91 CHECK_EQ(1, node->InputCount());
95 CHECK_EQ(2, node->InputCount());
104 // Wraps all "OPA0" nodes in "OPB1" operators by allocating new nodes.
105 class A0Wrapper FINAL : public Reducer {
107 explicit A0Wrapper(Graph* graph) : graph_(graph) {}
108 virtual Reduction Reduce(Node* node) OVERRIDE {
109 switch (node->op()->opcode()) {
111 CHECK_EQ(0, node->InputCount());
112 return Replace(graph_->NewNode(&OPB1, node));
120 // Wraps all "OPB0" nodes in two "OPC1" operators by allocating new nodes.
121 class B0Wrapper FINAL : public Reducer {
123 explicit B0Wrapper(Graph* graph) : graph_(graph) {}
124 virtual Reduction Reduce(Node* node) OVERRIDE {
125 switch (node->op()->opcode()) {
127 CHECK_EQ(0, node->InputCount());
128 return Replace(graph_->NewNode(&OPC1, graph_->NewNode(&OPC1, node)));
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()) {
141 CHECK_EQ(1, node->InputCount());
142 return Replace(node->InputAt(0));
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()) {
154 CHECK_EQ(1, node->InputCount());
155 return Replace(node->InputAt(0));
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()) {
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);
182 // Simply records the nodes visited.
183 class ReducerRecorder : public Reducer {
185 explicit ReducerRecorder(Zone* zone)
186 : set(NodeSet::key_compare(), NodeSet::allocator_type(zone)) {}
187 virtual Reduction Reduce(Node* node) {
191 void CheckContains(Node* node) {
192 CHECK_EQ(1, static_cast<int>(set.count(node)));
198 TEST(ReduceGraphFromEnd1) {
201 Node* n1 = graph.NewNode(&OPA0);
202 Node* end = graph.NewNode(&OPA1, n1);
205 GraphReducer reducer(&graph);
206 ReducerRecorder recorder(graph.zone());
207 reducer.AddReducer(&recorder);
208 reducer.ReduceGraph();
209 recorder.CheckContains(n1);
210 recorder.CheckContains(end);
214 TEST(ReduceGraphFromEnd2) {
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);
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);
234 TEST(ReduceInPlace1) {
237 Node* n1 = graph.NewNode(&OPA0);
238 Node* end = graph.NewNode(&OPA1, n1);
241 GraphReducer reducer(&graph);
243 reducer.AddReducer(&r);
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));
257 TEST(ReduceInPlace2) {
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);
266 GraphReducer reducer(&graph);
268 reducer.AddReducer(&r);
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));
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);
296 GraphReducer reducer(&graph);
297 NewABReducer r(&graph);
298 reducer.AddReducer(&r);
300 // Tests A* => B* while creating new nodes.
301 for (int i = 0; i < 3; i++) {
302 int before = graph.NodeCount();
303 reducer.ReduceGraph();
305 CHECK_NE(before, graph.NodeCount());
307 CHECK_EQ(before, graph.NodeCount());
309 Node* nend = graph.end();
310 CHECK_NE(end, nend); // end() should be updated too.
312 Node* nn2 = nend->InputAt(0);
313 Node* nn3 = nend->InputAt(1);
314 Node* nn1 = nn2->InputAt(0);
316 CHECK_EQ(nn1, nn3->InputAt(0));
318 CHECK_EQ(&OPB0, nn1->op());
319 CHECK_EQ(&OPB1, nn2->op());
320 CHECK_EQ(&OPB1, nn3->op());
321 CHECK_EQ(&OPB2, nend->op());
329 Node* end = graph.NewNode(&OPA0);
331 CHECK_EQ(1, graph.NodeCount());
333 GraphReducer reducer(&graph);
335 reducer.AddReducer(&r);
337 reducer.ReduceGraph();
338 CHECK_EQ(2, graph.NodeCount());
340 Node* nend = graph.end();
342 CHECK_EQ(&OPB1, nend->op());
343 CHECK_EQ(1, nend->InputCount());
344 CHECK_EQ(end, nend->InputAt(0));
351 Node* end = graph.NewNode(&OPB0);
353 CHECK_EQ(1, graph.NodeCount());
355 GraphReducer reducer(&graph);
357 reducer.AddReducer(&r);
359 reducer.ReduceGraph();
360 CHECK_EQ(3, graph.NodeCount());
362 Node* nend = graph.end();
364 CHECK_EQ(&OPC1, nend->op());
365 CHECK_EQ(1, nend->InputCount());
367 Node* n1 = nend->InputAt(0);
369 CHECK_EQ(&OPC1, n1->op());
370 CHECK_EQ(1, n1->InputCount());
371 CHECK_EQ(end, n1->InputAt(0));
378 Node* n1 = graph.NewNode(&OPA0);
379 Node* end = graph.NewNode(&OPA1, n1);
382 GraphReducer reducer(&graph);
384 reducer.AddReducer(&r);
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());
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);
406 GraphReducer reducer(&graph);
408 reducer.AddReducer(&r);
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());
426 // Tests reducing a chain of A1(A1(A1(A1(x)))) => x.
427 for (int i = 0; i < 8; i++) {
430 Node* n1 = graph.NewNode(&OPA0);
432 for (int j = 0; j < i; j++) {
433 end = graph.NewNode(&OPA1, end);
437 GraphReducer reducer(&graph);
439 reducer.AddReducer(&r);
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());
452 TEST(ReduceForward1) {
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);
461 GraphReducer reducer(&graph);
464 reducer.AddReducer(&r);
465 reducer.AddReducer(&f);
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());
474 CHECK_EQ(n1, end->InputAt(0));
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());
485 HandleAndZoneScope scope;
487 for (int i = 0; i < 6; i++) {
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.
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);
504 GraphReducer reducer(&graph);
505 reducer.AddReducer(&r);
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());
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)};
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]])};
531 Node* level1[] = {graph->NewNode(&OPA2, level2[p2[0]], level2[p2[1]]),
532 graph->NewNode(&OPA2, level2[p2[2]], level2[p2[3]])};
534 Node* end = graph->NewNode(&OPA2, level1[p1[0]], level1[p1[1]]);
539 TEST(SortForwardReduce) {
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};
550 for (int d = 4; d >= 1; d--) { // Construct permutation.
552 for (int z = 0; z < 4; z++) {
554 if (p == 0) p2[z] = d - 1;
561 GenDAG(&graph, p3, p2, p1);
563 GraphReducer reducer(&graph);
567 reducer.AddReducer(&r1);
568 reducer.AddReducer(&r2);
569 reducer.AddReducer(&r3);
571 reducer.ReduceGraph();
573 Node* end = graph.end();
574 CHECK_EQ(&OPB2, end->op());
575 Node* n1 = end->InputAt(0);
576 Node* n2 = end->InputAt(1);
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));
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++) {
598 Node* n1 = graph.NewNode(&OPA0);
599 Node* end = graph.NewNode(&OPA1, n1);
602 GraphReducer reducer(&graph);
603 InPlaceABReducer abr;
604 InPlaceBCReducer bcr;
606 reducer.AddReducer(&abr);
607 reducer.AddReducer(&bcr);
609 reducer.AddReducer(&bcr);
610 reducer.AddReducer(&abr);
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));
626 // Tests that a reducer is only applied once.
627 class OneTimeReducer : public Reducer {
629 OneTimeReducer(Reducer* reducer, Zone* zone)
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)));
635 return reducer_->Reduce(node);
642 TEST(OneTimeReduce1) {
645 Node* n1 = graph.NewNode(&OPA0);
646 Node* end = graph.NewNode(&OPA1, n1);
649 GraphReducer reducer(&graph);
651 OneTimeReducer once(&r, graph.zone());
652 reducer.AddReducer(&once);
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));