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:
Reduce(Node * node)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:
NewABReducer(Graph * graph)61 explicit NewABReducer(Graph* graph) : graph_(graph) {}
Reduce(Node * node)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:
Reduce(Node * node)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:
A0Wrapper(Graph * graph)107 explicit A0Wrapper(Graph* graph) : graph_(graph) {}
Reduce(Node * node)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:
B0Wrapper(Graph * graph)123 explicit B0Wrapper(Graph* graph) : graph_(graph) {}
Reduce(Node * node)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 {
Reduce(Node * node)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 {
Reduce(Node * node)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 {
Reduce(Node * node)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:
ReducerRecorder(Zone * zone)185 explicit ReducerRecorder(Zone* zone)
186 : set(NodeSet::key_compare(), NodeSet::allocator_type(zone)) {}
Reduce(Node * node)187 virtual Reduction Reduce(Node* node) {
188 set.insert(node);
189 return NoChange();
190 }
CheckContains(Node * node)191 void CheckContains(Node* node) {
192 CHECK_EQ(1, static_cast<int>(set.count(node)));
193 }
194 NodeSet set;
195 };
196
197
TEST(ReduceGraphFromEnd1)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
TEST(ReduceGraphFromEnd2)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
TEST(ReduceInPlace1)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
TEST(ReduceInPlace2)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
TEST(ReduceNew1)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
TEST(Wrapping1)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
TEST(Wrapping2)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
TEST(Forwarding1)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
TEST(Forwarding2)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
TEST(Forwarding3)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
TEST(ReduceForward1)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
TEST(Sorter1)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.
GenDAG(Graph * graph,int * p3,int * p2,int * p1)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
TEST(SortForwardReduce)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
TEST(Order)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:
OneTimeReducer(Reducer * reducer,Zone * zone)629 OneTimeReducer(Reducer* reducer, Zone* zone)
630 : reducer_(reducer),
631 nodes_(NodeSet::key_compare(), NodeSet::allocator_type(zone)) {}
Reduce(Node * node)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
TEST(OneTimeReduce1)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