test-graph-reducer.cc revision b8a8cc1952d61a2f3a2568848933943a543b5d3e 
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
11using namespace v8::internal;
12using namespace v8::internal::compiler;
13
14const uint8_t OPCODE_A0 = 10;
15const uint8_t OPCODE_A1 = 11;
16const uint8_t OPCODE_A2 = 12;
17const uint8_t OPCODE_B0 = 20;
18const uint8_t OPCODE_B1 = 21;
19const uint8_t OPCODE_B2 = 22;
20const uint8_t OPCODE_C0 = 30;
21const uint8_t OPCODE_C1 = 31;
22const uint8_t OPCODE_C2 = 32;
23
24static SimpleOperator OPA0(OPCODE_A0, Operator::kNoWrite, 0, 0, "opa0");
25static SimpleOperator OPA1(OPCODE_A1, Operator::kNoWrite, 1, 0, "opa1");
26static SimpleOperator OPA2(OPCODE_A2, Operator::kNoWrite, 2, 0, "opa2");
27static SimpleOperator OPB0(OPCODE_B0, Operator::kNoWrite, 0, 0, "opa0");
28static SimpleOperator OPB1(OPCODE_B1, Operator::kNoWrite, 1, 0, "opa1");
29static SimpleOperator OPB2(OPCODE_B2, Operator::kNoWrite, 2, 0, "opa2");
30static SimpleOperator OPC0(OPCODE_C0, Operator::kNoWrite, 0, 0, "opc0");
31static SimpleOperator OPC1(OPCODE_C1, Operator::kNoWrite, 1, 0, "opc1");
32static SimpleOperator OPC2(OPCODE_C2, Operator::kNoWrite, 2, 0, "opc2");
33
34
35// Replaces all "A" operators with "B" operators without creating new nodes.
36class 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.
59class 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.
82class 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.
105class 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.
121class 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.
137class 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.
150class 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.
163class 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.
183class 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
198TEST(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
214TEST(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
234TEST(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
257TEST(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
287TEST(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
326TEST(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
348TEST(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
375TEST(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
397TEST(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
425TEST(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
452TEST(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
484TEST(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.
521void 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
539TEST(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
592TEST(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.
627class 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
642TEST(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