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 #include "test/cctest/cctest.h"
7 
8 #include "src/compiler/common-operator.h"
9 #include "src/compiler/generic-node-inl.h"
10 #include "src/compiler/generic-node.h"
11 #include "src/compiler/graph.h"
12 #include "src/compiler/graph-visualizer.h"
13 #include "src/compiler/js-operator.h"
14 #include "src/compiler/machine-operator.h"
15 #include "src/compiler/node.h"
16 #include "src/compiler/operator.h"
17 #include "src/compiler/schedule.h"
18 #include "src/compiler/scheduler.h"
19 #include "src/compiler/verifier.h"
20 
21 using namespace v8::internal;
22 using namespace v8::internal::compiler;
23 
24 // TODO(titzer): pull RPO tests out to their own file.
25 struct TestLoop {
26   int count;
27   BasicBlock** nodes;
headerTestLoop28   BasicBlock* header() { return nodes[0]; }
lastTestLoop29   BasicBlock* last() { return nodes[count - 1]; }
~TestLoopTestLoop30   ~TestLoop() { delete[] nodes; }
31 };
32 
33 
CreateLoop(Schedule * schedule,int count)34 static TestLoop* CreateLoop(Schedule* schedule, int count) {
35   TestLoop* loop = new TestLoop();
36   loop->count = count;
37   loop->nodes = new BasicBlock* [count];
38   for (int i = 0; i < count; i++) {
39     loop->nodes[i] = schedule->NewBasicBlock();
40     if (i > 0) schedule->AddSuccessor(loop->nodes[i - 1], loop->nodes[i]);
41   }
42   schedule->AddSuccessor(loop->nodes[count - 1], loop->nodes[0]);
43   return loop;
44 }
45 
46 
CheckRPONumbers(BasicBlockVector * order,int expected,bool loops_allowed)47 static void CheckRPONumbers(BasicBlockVector* order, int expected,
48                             bool loops_allowed) {
49   CHECK_EQ(expected, static_cast<int>(order->size()));
50   for (int i = 0; i < static_cast<int>(order->size()); i++) {
51     CHECK(order->at(i)->rpo_number_ == i);
52     if (!loops_allowed) CHECK_LT(order->at(i)->loop_end_, 0);
53   }
54 }
55 
56 
CheckLoopContains(BasicBlock ** blocks,int body_size)57 static void CheckLoopContains(BasicBlock** blocks, int body_size) {
58   BasicBlock* header = blocks[0];
59   CHECK_GT(header->loop_end_, 0);
60   CHECK_EQ(body_size, (header->loop_end_ - header->rpo_number_));
61   for (int i = 0; i < body_size; i++) {
62     int num = blocks[i]->rpo_number_;
63     CHECK(num >= header->rpo_number_ && num < header->loop_end_);
64     CHECK(header->LoopContains(blocks[i]));
65     CHECK(header->IsLoopHeader() || blocks[i]->loop_header_ == header);
66   }
67 }
68 
69 
GetScheduledNodeCount(Schedule * schedule)70 static int GetScheduledNodeCount(Schedule* schedule) {
71   int node_count = 0;
72   for (BasicBlockVectorIter i = schedule->rpo_order()->begin();
73        i != schedule->rpo_order()->end(); ++i) {
74     BasicBlock* block = *i;
75     for (BasicBlock::const_iterator j = block->begin(); j != block->end();
76          ++j) {
77       ++node_count;
78     }
79     BasicBlock::Control control = block->control_;
80     if (control != BasicBlock::kNone) {
81       ++node_count;
82     }
83   }
84   return node_count;
85 }
86 
87 
ComputeAndVerifySchedule(int expected,Graph * graph)88 static Schedule* ComputeAndVerifySchedule(int expected, Graph* graph) {
89   if (FLAG_trace_turbo) {
90     OFStream os(stdout);
91     os << AsDOT(*graph);
92   }
93 
94   Schedule* schedule = Scheduler::ComputeSchedule(graph);
95 
96   if (FLAG_trace_turbo_scheduler) {
97     OFStream os(stdout);
98     os << *schedule << endl;
99   }
100   ScheduleVerifier::Run(schedule);
101   CHECK_EQ(expected, GetScheduledNodeCount(schedule));
102   return schedule;
103 }
104 
105 
TEST(RPODegenerate1)106 TEST(RPODegenerate1) {
107   HandleAndZoneScope scope;
108   Schedule schedule(scope.main_zone());
109 
110   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
111   CheckRPONumbers(order, 1, false);
112   CHECK_EQ(schedule.start(), order->at(0));
113 }
114 
115 
TEST(RPODegenerate2)116 TEST(RPODegenerate2) {
117   HandleAndZoneScope scope;
118   Schedule schedule(scope.main_zone());
119 
120   schedule.AddGoto(schedule.start(), schedule.end());
121   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
122   CheckRPONumbers(order, 2, false);
123   CHECK_EQ(schedule.start(), order->at(0));
124   CHECK_EQ(schedule.end(), order->at(1));
125 }
126 
127 
TEST(RPOLine)128 TEST(RPOLine) {
129   HandleAndZoneScope scope;
130 
131   for (int i = 0; i < 10; i++) {
132     Schedule schedule(scope.main_zone());
133 
134     BasicBlock* last = schedule.start();
135     for (int j = 0; j < i; j++) {
136       BasicBlock* block = schedule.NewBasicBlock();
137       schedule.AddGoto(last, block);
138       last = block;
139     }
140     BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
141     CheckRPONumbers(order, 1 + i, false);
142 
143     Schedule::BasicBlocks blocks(schedule.all_blocks());
144     for (Schedule::BasicBlocks::iterator iter = blocks.begin();
145          iter != blocks.end(); ++iter) {
146       BasicBlock* block = *iter;
147       if (block->rpo_number_ >= 0 && block->SuccessorCount() == 1) {
148         CHECK(block->rpo_number_ + 1 == block->SuccessorAt(0)->rpo_number_);
149       }
150     }
151   }
152 }
153 
154 
TEST(RPOSelfLoop)155 TEST(RPOSelfLoop) {
156   HandleAndZoneScope scope;
157   Schedule schedule(scope.main_zone());
158   schedule.AddSuccessor(schedule.start(), schedule.start());
159   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
160   CheckRPONumbers(order, 1, true);
161   BasicBlock* loop[] = {schedule.start()};
162   CheckLoopContains(loop, 1);
163 }
164 
165 
TEST(RPOEntryLoop)166 TEST(RPOEntryLoop) {
167   HandleAndZoneScope scope;
168   Schedule schedule(scope.main_zone());
169   schedule.AddSuccessor(schedule.start(), schedule.end());
170   schedule.AddSuccessor(schedule.end(), schedule.start());
171   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
172   CheckRPONumbers(order, 2, true);
173   BasicBlock* loop[] = {schedule.start(), schedule.end()};
174   CheckLoopContains(loop, 2);
175 }
176 
177 
TEST(RPOEndLoop)178 TEST(RPOEndLoop) {
179   HandleAndZoneScope scope;
180   Schedule schedule(scope.main_zone());
181   SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 2));
182   schedule.AddSuccessor(schedule.start(), loop1->header());
183   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
184   CheckRPONumbers(order, 3, true);
185   CheckLoopContains(loop1->nodes, loop1->count);
186 }
187 
188 
TEST(RPOEndLoopNested)189 TEST(RPOEndLoopNested) {
190   HandleAndZoneScope scope;
191   Schedule schedule(scope.main_zone());
192   SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 2));
193   schedule.AddSuccessor(schedule.start(), loop1->header());
194   schedule.AddSuccessor(loop1->last(), schedule.start());
195   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
196   CheckRPONumbers(order, 3, true);
197   CheckLoopContains(loop1->nodes, loop1->count);
198 }
199 
200 
TEST(RPODiamond)201 TEST(RPODiamond) {
202   HandleAndZoneScope scope;
203   Schedule schedule(scope.main_zone());
204 
205   BasicBlock* A = schedule.start();
206   BasicBlock* B = schedule.NewBasicBlock();
207   BasicBlock* C = schedule.NewBasicBlock();
208   BasicBlock* D = schedule.end();
209 
210   schedule.AddSuccessor(A, B);
211   schedule.AddSuccessor(A, C);
212   schedule.AddSuccessor(B, D);
213   schedule.AddSuccessor(C, D);
214 
215   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
216   CheckRPONumbers(order, 4, false);
217 
218   CHECK_EQ(0, A->rpo_number_);
219   CHECK((B->rpo_number_ == 1 && C->rpo_number_ == 2) ||
220         (B->rpo_number_ == 2 && C->rpo_number_ == 1));
221   CHECK_EQ(3, D->rpo_number_);
222 }
223 
224 
TEST(RPOLoop1)225 TEST(RPOLoop1) {
226   HandleAndZoneScope scope;
227   Schedule schedule(scope.main_zone());
228 
229   BasicBlock* A = schedule.start();
230   BasicBlock* B = schedule.NewBasicBlock();
231   BasicBlock* C = schedule.NewBasicBlock();
232   BasicBlock* D = schedule.end();
233 
234   schedule.AddSuccessor(A, B);
235   schedule.AddSuccessor(B, C);
236   schedule.AddSuccessor(C, B);
237   schedule.AddSuccessor(C, D);
238 
239   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
240   CheckRPONumbers(order, 4, true);
241   BasicBlock* loop[] = {B, C};
242   CheckLoopContains(loop, 2);
243 }
244 
245 
TEST(RPOLoop2)246 TEST(RPOLoop2) {
247   HandleAndZoneScope scope;
248   Schedule schedule(scope.main_zone());
249 
250   BasicBlock* A = schedule.start();
251   BasicBlock* B = schedule.NewBasicBlock();
252   BasicBlock* C = schedule.NewBasicBlock();
253   BasicBlock* D = schedule.end();
254 
255   schedule.AddSuccessor(A, B);
256   schedule.AddSuccessor(B, C);
257   schedule.AddSuccessor(C, B);
258   schedule.AddSuccessor(B, D);
259 
260   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
261   CheckRPONumbers(order, 4, true);
262   BasicBlock* loop[] = {B, C};
263   CheckLoopContains(loop, 2);
264 }
265 
266 
TEST(RPOLoopN)267 TEST(RPOLoopN) {
268   HandleAndZoneScope scope;
269 
270   for (int i = 0; i < 11; i++) {
271     Schedule schedule(scope.main_zone());
272     BasicBlock* A = schedule.start();
273     BasicBlock* B = schedule.NewBasicBlock();
274     BasicBlock* C = schedule.NewBasicBlock();
275     BasicBlock* D = schedule.NewBasicBlock();
276     BasicBlock* E = schedule.NewBasicBlock();
277     BasicBlock* F = schedule.NewBasicBlock();
278     BasicBlock* G = schedule.end();
279 
280     schedule.AddSuccessor(A, B);
281     schedule.AddSuccessor(B, C);
282     schedule.AddSuccessor(C, D);
283     schedule.AddSuccessor(D, E);
284     schedule.AddSuccessor(E, F);
285     schedule.AddSuccessor(F, B);
286     schedule.AddSuccessor(B, G);
287 
288     // Throw in extra backedges from time to time.
289     if (i == 1) schedule.AddSuccessor(B, B);
290     if (i == 2) schedule.AddSuccessor(C, B);
291     if (i == 3) schedule.AddSuccessor(D, B);
292     if (i == 4) schedule.AddSuccessor(E, B);
293     if (i == 5) schedule.AddSuccessor(F, B);
294 
295     // Throw in extra loop exits from time to time.
296     if (i == 6) schedule.AddSuccessor(B, G);
297     if (i == 7) schedule.AddSuccessor(C, G);
298     if (i == 8) schedule.AddSuccessor(D, G);
299     if (i == 9) schedule.AddSuccessor(E, G);
300     if (i == 10) schedule.AddSuccessor(F, G);
301 
302     BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
303     CheckRPONumbers(order, 7, true);
304     BasicBlock* loop[] = {B, C, D, E, F};
305     CheckLoopContains(loop, 5);
306   }
307 }
308 
309 
TEST(RPOLoopNest1)310 TEST(RPOLoopNest1) {
311   HandleAndZoneScope scope;
312   Schedule schedule(scope.main_zone());
313 
314   BasicBlock* A = schedule.start();
315   BasicBlock* B = schedule.NewBasicBlock();
316   BasicBlock* C = schedule.NewBasicBlock();
317   BasicBlock* D = schedule.NewBasicBlock();
318   BasicBlock* E = schedule.NewBasicBlock();
319   BasicBlock* F = schedule.end();
320 
321   schedule.AddSuccessor(A, B);
322   schedule.AddSuccessor(B, C);
323   schedule.AddSuccessor(C, D);
324   schedule.AddSuccessor(D, C);
325   schedule.AddSuccessor(D, E);
326   schedule.AddSuccessor(E, B);
327   schedule.AddSuccessor(E, F);
328 
329   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
330   CheckRPONumbers(order, 6, true);
331   BasicBlock* loop1[] = {B, C, D, E};
332   CheckLoopContains(loop1, 4);
333 
334   BasicBlock* loop2[] = {C, D};
335   CheckLoopContains(loop2, 2);
336 }
337 
338 
TEST(RPOLoopNest2)339 TEST(RPOLoopNest2) {
340   HandleAndZoneScope scope;
341   Schedule schedule(scope.main_zone());
342 
343   BasicBlock* A = schedule.start();
344   BasicBlock* B = schedule.NewBasicBlock();
345   BasicBlock* C = schedule.NewBasicBlock();
346   BasicBlock* D = schedule.NewBasicBlock();
347   BasicBlock* E = schedule.NewBasicBlock();
348   BasicBlock* F = schedule.NewBasicBlock();
349   BasicBlock* G = schedule.NewBasicBlock();
350   BasicBlock* H = schedule.end();
351 
352   schedule.AddSuccessor(A, B);
353   schedule.AddSuccessor(B, C);
354   schedule.AddSuccessor(C, D);
355   schedule.AddSuccessor(D, E);
356   schedule.AddSuccessor(E, F);
357   schedule.AddSuccessor(F, G);
358   schedule.AddSuccessor(G, H);
359 
360   schedule.AddSuccessor(E, D);
361   schedule.AddSuccessor(F, C);
362   schedule.AddSuccessor(G, B);
363 
364   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
365   CheckRPONumbers(order, 8, true);
366   BasicBlock* loop1[] = {B, C, D, E, F, G};
367   CheckLoopContains(loop1, 6);
368 
369   BasicBlock* loop2[] = {C, D, E, F};
370   CheckLoopContains(loop2, 4);
371 
372   BasicBlock* loop3[] = {D, E};
373   CheckLoopContains(loop3, 2);
374 }
375 
376 
TEST(RPOLoopFollow1)377 TEST(RPOLoopFollow1) {
378   HandleAndZoneScope scope;
379   Schedule schedule(scope.main_zone());
380 
381   SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 1));
382   SmartPointer<TestLoop> loop2(CreateLoop(&schedule, 1));
383 
384   BasicBlock* A = schedule.start();
385   BasicBlock* E = schedule.end();
386 
387   schedule.AddSuccessor(A, loop1->header());
388   schedule.AddSuccessor(loop1->header(), loop2->header());
389   schedule.AddSuccessor(loop2->last(), E);
390 
391   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
392 
393   CheckLoopContains(loop1->nodes, loop1->count);
394 
395   CHECK_EQ(schedule.BasicBlockCount(), static_cast<int>(order->size()));
396   CheckLoopContains(loop1->nodes, loop1->count);
397   CheckLoopContains(loop2->nodes, loop2->count);
398 }
399 
400 
TEST(RPOLoopFollow2)401 TEST(RPOLoopFollow2) {
402   HandleAndZoneScope scope;
403   Schedule schedule(scope.main_zone());
404 
405   SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 1));
406   SmartPointer<TestLoop> loop2(CreateLoop(&schedule, 1));
407 
408   BasicBlock* A = schedule.start();
409   BasicBlock* S = schedule.NewBasicBlock();
410   BasicBlock* E = schedule.end();
411 
412   schedule.AddSuccessor(A, loop1->header());
413   schedule.AddSuccessor(loop1->header(), S);
414   schedule.AddSuccessor(S, loop2->header());
415   schedule.AddSuccessor(loop2->last(), E);
416 
417   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
418 
419   CheckLoopContains(loop1->nodes, loop1->count);
420 
421   CHECK_EQ(schedule.BasicBlockCount(), static_cast<int>(order->size()));
422   CheckLoopContains(loop1->nodes, loop1->count);
423   CheckLoopContains(loop2->nodes, loop2->count);
424 }
425 
426 
TEST(RPOLoopFollowN)427 TEST(RPOLoopFollowN) {
428   HandleAndZoneScope scope;
429 
430   for (int size = 1; size < 5; size++) {
431     for (int exit = 0; exit < size; exit++) {
432       Schedule schedule(scope.main_zone());
433       SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size));
434       SmartPointer<TestLoop> loop2(CreateLoop(&schedule, size));
435       BasicBlock* A = schedule.start();
436       BasicBlock* E = schedule.end();
437 
438       schedule.AddSuccessor(A, loop1->header());
439       schedule.AddSuccessor(loop1->nodes[exit], loop2->header());
440       schedule.AddSuccessor(loop2->nodes[exit], E);
441       BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
442       CheckLoopContains(loop1->nodes, loop1->count);
443 
444       CHECK_EQ(schedule.BasicBlockCount(), static_cast<int>(order->size()));
445       CheckLoopContains(loop1->nodes, loop1->count);
446       CheckLoopContains(loop2->nodes, loop2->count);
447     }
448   }
449 }
450 
451 
TEST(RPONestedLoopFollow1)452 TEST(RPONestedLoopFollow1) {
453   HandleAndZoneScope scope;
454   Schedule schedule(scope.main_zone());
455 
456   SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 1));
457   SmartPointer<TestLoop> loop2(CreateLoop(&schedule, 1));
458 
459   BasicBlock* A = schedule.start();
460   BasicBlock* B = schedule.NewBasicBlock();
461   BasicBlock* C = schedule.NewBasicBlock();
462   BasicBlock* E = schedule.end();
463 
464   schedule.AddSuccessor(A, B);
465   schedule.AddSuccessor(B, loop1->header());
466   schedule.AddSuccessor(loop1->header(), loop2->header());
467   schedule.AddSuccessor(loop2->last(), C);
468   schedule.AddSuccessor(C, E);
469   schedule.AddSuccessor(C, B);
470 
471   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
472 
473   CheckLoopContains(loop1->nodes, loop1->count);
474 
475   CHECK_EQ(schedule.BasicBlockCount(), static_cast<int>(order->size()));
476   CheckLoopContains(loop1->nodes, loop1->count);
477   CheckLoopContains(loop2->nodes, loop2->count);
478 
479   BasicBlock* loop3[] = {B, loop1->nodes[0], loop2->nodes[0], C};
480   CheckLoopContains(loop3, 4);
481 }
482 
483 
TEST(RPOLoopBackedges1)484 TEST(RPOLoopBackedges1) {
485   HandleAndZoneScope scope;
486 
487   int size = 8;
488   for (int i = 0; i < size; i++) {
489     for (int j = 0; j < size; j++) {
490       Schedule schedule(scope.main_zone());
491       BasicBlock* A = schedule.start();
492       BasicBlock* E = schedule.end();
493 
494       SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size));
495       schedule.AddSuccessor(A, loop1->header());
496       schedule.AddSuccessor(loop1->last(), E);
497 
498       schedule.AddSuccessor(loop1->nodes[i], loop1->header());
499       schedule.AddSuccessor(loop1->nodes[j], E);
500 
501       BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
502       CheckRPONumbers(order, schedule.BasicBlockCount(), true);
503       CheckLoopContains(loop1->nodes, loop1->count);
504     }
505   }
506 }
507 
508 
TEST(RPOLoopOutedges1)509 TEST(RPOLoopOutedges1) {
510   HandleAndZoneScope scope;
511 
512   int size = 8;
513   for (int i = 0; i < size; i++) {
514     for (int j = 0; j < size; j++) {
515       Schedule schedule(scope.main_zone());
516       BasicBlock* A = schedule.start();
517       BasicBlock* D = schedule.NewBasicBlock();
518       BasicBlock* E = schedule.end();
519 
520       SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size));
521       schedule.AddSuccessor(A, loop1->header());
522       schedule.AddSuccessor(loop1->last(), E);
523 
524       schedule.AddSuccessor(loop1->nodes[i], loop1->header());
525       schedule.AddSuccessor(loop1->nodes[j], D);
526       schedule.AddSuccessor(D, E);
527 
528       BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
529       CheckRPONumbers(order, schedule.BasicBlockCount(), true);
530       CheckLoopContains(loop1->nodes, loop1->count);
531     }
532   }
533 }
534 
535 
TEST(RPOLoopOutedges2)536 TEST(RPOLoopOutedges2) {
537   HandleAndZoneScope scope;
538 
539   int size = 8;
540   for (int i = 0; i < size; i++) {
541     Schedule schedule(scope.main_zone());
542     BasicBlock* A = schedule.start();
543     BasicBlock* E = schedule.end();
544 
545     SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size));
546     schedule.AddSuccessor(A, loop1->header());
547     schedule.AddSuccessor(loop1->last(), E);
548 
549     for (int j = 0; j < size; j++) {
550       BasicBlock* O = schedule.NewBasicBlock();
551       schedule.AddSuccessor(loop1->nodes[j], O);
552       schedule.AddSuccessor(O, E);
553     }
554 
555     BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
556     CheckRPONumbers(order, schedule.BasicBlockCount(), true);
557     CheckLoopContains(loop1->nodes, loop1->count);
558   }
559 }
560 
561 
TEST(RPOLoopOutloops1)562 TEST(RPOLoopOutloops1) {
563   HandleAndZoneScope scope;
564 
565   int size = 8;
566   for (int i = 0; i < size; i++) {
567     Schedule schedule(scope.main_zone());
568     BasicBlock* A = schedule.start();
569     BasicBlock* E = schedule.end();
570     SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size));
571     schedule.AddSuccessor(A, loop1->header());
572     schedule.AddSuccessor(loop1->last(), E);
573 
574     TestLoop** loopN = new TestLoop* [size];
575     for (int j = 0; j < size; j++) {
576       loopN[j] = CreateLoop(&schedule, 2);
577       schedule.AddSuccessor(loop1->nodes[j], loopN[j]->header());
578       schedule.AddSuccessor(loopN[j]->last(), E);
579     }
580 
581     BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
582     CheckRPONumbers(order, schedule.BasicBlockCount(), true);
583     CheckLoopContains(loop1->nodes, loop1->count);
584 
585     for (int j = 0; j < size; j++) {
586       CheckLoopContains(loopN[j]->nodes, loopN[j]->count);
587       delete loopN[j];
588     }
589     delete[] loopN;
590   }
591 }
592 
593 
TEST(RPOLoopMultibackedge)594 TEST(RPOLoopMultibackedge) {
595   HandleAndZoneScope scope;
596   Schedule schedule(scope.main_zone());
597 
598   BasicBlock* A = schedule.start();
599   BasicBlock* B = schedule.NewBasicBlock();
600   BasicBlock* C = schedule.NewBasicBlock();
601   BasicBlock* D = schedule.end();
602   BasicBlock* E = schedule.NewBasicBlock();
603 
604   schedule.AddSuccessor(A, B);
605   schedule.AddSuccessor(B, C);
606   schedule.AddSuccessor(B, D);
607   schedule.AddSuccessor(B, E);
608   schedule.AddSuccessor(C, B);
609   schedule.AddSuccessor(D, B);
610   schedule.AddSuccessor(E, B);
611 
612   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
613   CheckRPONumbers(order, 5, true);
614 
615   BasicBlock* loop1[] = {B, C, D, E};
616   CheckLoopContains(loop1, 4);
617 }
618 
619 
TEST(BuildScheduleEmpty)620 TEST(BuildScheduleEmpty) {
621   HandleAndZoneScope scope;
622   Graph graph(scope.main_zone());
623   CommonOperatorBuilder builder(scope.main_zone());
624   graph.SetStart(graph.NewNode(builder.Start(0)));
625   graph.SetEnd(graph.NewNode(builder.End(), graph.start()));
626 
627   USE(Scheduler::ComputeSchedule(&graph));
628 }
629 
630 
TEST(BuildScheduleOneParameter)631 TEST(BuildScheduleOneParameter) {
632   HandleAndZoneScope scope;
633   Graph graph(scope.main_zone());
634   CommonOperatorBuilder builder(scope.main_zone());
635   graph.SetStart(graph.NewNode(builder.Start(0)));
636 
637   Node* p1 = graph.NewNode(builder.Parameter(0), graph.start());
638   Node* ret = graph.NewNode(builder.Return(), p1, graph.start(), graph.start());
639 
640   graph.SetEnd(graph.NewNode(builder.End(), ret));
641 
642   USE(Scheduler::ComputeSchedule(&graph));
643 }
644 
645 
TEST(BuildScheduleIfSplit)646 TEST(BuildScheduleIfSplit) {
647   HandleAndZoneScope scope;
648   Graph graph(scope.main_zone());
649   CommonOperatorBuilder builder(scope.main_zone());
650   JSOperatorBuilder js_builder(scope.main_zone());
651   graph.SetStart(graph.NewNode(builder.Start(3)));
652 
653   Node* p1 = graph.NewNode(builder.Parameter(0), graph.start());
654   Node* p2 = graph.NewNode(builder.Parameter(1), graph.start());
655   Node* p3 = graph.NewNode(builder.Parameter(2), graph.start());
656   Node* p4 = graph.NewNode(builder.Parameter(3), graph.start());
657   Node* p5 = graph.NewNode(builder.Parameter(4), graph.start());
658   Node* cmp = graph.NewNode(js_builder.LessThanOrEqual(), p1, p2, p3,
659                             graph.start(), graph.start());
660   Node* branch = graph.NewNode(builder.Branch(), cmp, graph.start());
661   Node* true_branch = graph.NewNode(builder.IfTrue(), branch);
662   Node* false_branch = graph.NewNode(builder.IfFalse(), branch);
663 
664   Node* ret1 = graph.NewNode(builder.Return(), p4, graph.start(), true_branch);
665   Node* ret2 = graph.NewNode(builder.Return(), p5, graph.start(), false_branch);
666   Node* merge = graph.NewNode(builder.Merge(2), ret1, ret2);
667   graph.SetEnd(graph.NewNode(builder.End(), merge));
668 
669   ComputeAndVerifySchedule(13, &graph);
670 }
671 
672 
TEST(BuildScheduleIfSplitWithEffects)673 TEST(BuildScheduleIfSplitWithEffects) {
674   HandleAndZoneScope scope;
675   Isolate* isolate = scope.main_isolate();
676   Graph graph(scope.main_zone());
677   CommonOperatorBuilder common_builder(scope.main_zone());
678   JSOperatorBuilder js_builder(scope.main_zone());
679   const Operator* op;
680 
681   Handle<Object> object =
682       Handle<Object>(isolate->heap()->undefined_value(), isolate);
683   Unique<Object> unique_constant = Unique<Object>::CreateUninitialized(object);
684 
685   // Manually transcripted code for:
686   // function turbo_fan_test(a, b, c, y) {
687   //   if (a < b) {
688   //     return a + b - c * c - a + y;
689   //   } else {
690   //     return c * c - a;
691   //   }
692   // }
693   op = common_builder.Start(0);
694   Node* n0 = graph.NewNode(op);
695   USE(n0);
696   Node* nil = graph.NewNode(common_builder.Dead());
697   op = common_builder.End();
698   Node* n23 = graph.NewNode(op, nil);
699   USE(n23);
700   op = common_builder.Merge(2);
701   Node* n22 = graph.NewNode(op, nil, nil);
702   USE(n22);
703   op = common_builder.Return();
704   Node* n16 = graph.NewNode(op, nil, nil, nil);
705   USE(n16);
706   op = js_builder.Add();
707   Node* n15 = graph.NewNode(op, nil, nil, nil, nil, nil);
708   USE(n15);
709   op = js_builder.Subtract();
710   Node* n14 = graph.NewNode(op, nil, nil, nil, nil, nil);
711   USE(n14);
712   op = js_builder.Subtract();
713   Node* n13 = graph.NewNode(op, nil, nil, nil, nil, nil);
714   USE(n13);
715   op = js_builder.Add();
716   Node* n11 = graph.NewNode(op, nil, nil, nil, nil, nil);
717   USE(n11);
718   op = common_builder.Parameter(0);
719   Node* n2 = graph.NewNode(op, n0);
720   USE(n2);
721   n11->ReplaceInput(0, n2);
722   op = common_builder.Parameter(0);
723   Node* n3 = graph.NewNode(op, n0);
724   USE(n3);
725   n11->ReplaceInput(1, n3);
726   op = common_builder.HeapConstant(unique_constant);
727   Node* n7 = graph.NewNode(op);
728   USE(n7);
729   n11->ReplaceInput(2, n7);
730   op = js_builder.LessThan();
731   Node* n8 = graph.NewNode(op, nil, nil, nil, nil, nil);
732   USE(n8);
733   n8->ReplaceInput(0, n2);
734   n8->ReplaceInput(1, n3);
735   n8->ReplaceInput(2, n7);
736   n8->ReplaceInput(3, n0);
737   n8->ReplaceInput(4, n0);
738   n11->ReplaceInput(3, n8);
739   op = common_builder.IfTrue();
740   Node* n10 = graph.NewNode(op, nil);
741   USE(n10);
742   op = common_builder.Branch();
743   Node* n9 = graph.NewNode(op, nil, nil);
744   USE(n9);
745   n9->ReplaceInput(0, n8);
746   n9->ReplaceInput(1, n0);
747   n10->ReplaceInput(0, n9);
748   n11->ReplaceInput(4, n10);
749   n13->ReplaceInput(0, n11);
750   op = js_builder.Multiply();
751   Node* n12 = graph.NewNode(op, nil, nil, nil, nil, nil);
752   USE(n12);
753   op = common_builder.Parameter(0);
754   Node* n4 = graph.NewNode(op, n0);
755   USE(n4);
756   n12->ReplaceInput(0, n4);
757   n12->ReplaceInput(1, n4);
758   n12->ReplaceInput(2, n7);
759   n12->ReplaceInput(3, n11);
760   n12->ReplaceInput(4, n10);
761   n13->ReplaceInput(1, n12);
762   n13->ReplaceInput(2, n7);
763   n13->ReplaceInput(3, n12);
764   n13->ReplaceInput(4, n10);
765   n14->ReplaceInput(0, n13);
766   n14->ReplaceInput(1, n2);
767   n14->ReplaceInput(2, n7);
768   n14->ReplaceInput(3, n13);
769   n14->ReplaceInput(4, n10);
770   n15->ReplaceInput(0, n14);
771   op = common_builder.Parameter(0);
772   Node* n5 = graph.NewNode(op, n0);
773   USE(n5);
774   n15->ReplaceInput(1, n5);
775   n15->ReplaceInput(2, n7);
776   n15->ReplaceInput(3, n14);
777   n15->ReplaceInput(4, n10);
778   n16->ReplaceInput(0, n15);
779   n16->ReplaceInput(1, n15);
780   n16->ReplaceInput(2, n10);
781   n22->ReplaceInput(0, n16);
782   op = common_builder.Return();
783   Node* n21 = graph.NewNode(op, nil, nil, nil);
784   USE(n21);
785   op = js_builder.Subtract();
786   Node* n20 = graph.NewNode(op, nil, nil, nil, nil, nil);
787   USE(n20);
788   op = js_builder.Multiply();
789   Node* n19 = graph.NewNode(op, nil, nil, nil, nil, nil);
790   USE(n19);
791   n19->ReplaceInput(0, n4);
792   n19->ReplaceInput(1, n4);
793   n19->ReplaceInput(2, n7);
794   n19->ReplaceInput(3, n8);
795   op = common_builder.IfFalse();
796   Node* n18 = graph.NewNode(op, nil);
797   USE(n18);
798   n18->ReplaceInput(0, n9);
799   n19->ReplaceInput(4, n18);
800   n20->ReplaceInput(0, n19);
801   n20->ReplaceInput(1, n2);
802   n20->ReplaceInput(2, n7);
803   n20->ReplaceInput(3, n19);
804   n20->ReplaceInput(4, n18);
805   n21->ReplaceInput(0, n20);
806   n21->ReplaceInput(1, n20);
807   n21->ReplaceInput(2, n18);
808   n22->ReplaceInput(1, n21);
809   n23->ReplaceInput(0, n22);
810 
811   graph.SetStart(n0);
812   graph.SetEnd(n23);
813 
814   ComputeAndVerifySchedule(20, &graph);
815 }
816 
817 
TEST(BuildScheduleSimpleLoop)818 TEST(BuildScheduleSimpleLoop) {
819   HandleAndZoneScope scope;
820   Isolate* isolate = scope.main_isolate();
821   Graph graph(scope.main_zone());
822   CommonOperatorBuilder common_builder(scope.main_zone());
823   JSOperatorBuilder js_builder(scope.main_zone());
824   const Operator* op;
825 
826   Handle<Object> object =
827       Handle<Object>(isolate->heap()->undefined_value(), isolate);
828   Unique<Object> unique_constant = Unique<Object>::CreateUninitialized(object);
829 
830   // Manually transcripted code for:
831   // function turbo_fan_test(a, b) {
832   //   while (a < b) {
833   //     a++;
834   //   }
835   //   return a;
836   // }
837   op = common_builder.Start(0);
838   Node* n0 = graph.NewNode(op);
839   USE(n0);
840   Node* nil = graph.NewNode(common_builder.Dead());
841   op = common_builder.End();
842   Node* n20 = graph.NewNode(op, nil);
843   USE(n20);
844   op = common_builder.Return();
845   Node* n19 = graph.NewNode(op, nil, nil, nil);
846   USE(n19);
847   op = common_builder.Phi(kMachAnyTagged, 2);
848   Node* n8 = graph.NewNode(op, nil, nil, nil);
849   USE(n8);
850   op = common_builder.Parameter(0);
851   Node* n2 = graph.NewNode(op, n0);
852   USE(n2);
853   n8->ReplaceInput(0, n2);
854   op = js_builder.Add();
855   Node* n18 = graph.NewNode(op, nil, nil, nil, nil, nil);
856   USE(n18);
857   op = js_builder.ToNumber();
858   Node* n16 = graph.NewNode(op, nil, nil, nil, nil);
859   USE(n16);
860   n16->ReplaceInput(0, n8);
861   op = common_builder.HeapConstant(unique_constant);
862   Node* n5 = graph.NewNode(op);
863   USE(n5);
864   n16->ReplaceInput(1, n5);
865   op = js_builder.LessThan();
866   Node* n12 = graph.NewNode(op, nil, nil, nil, nil, nil);
867   USE(n12);
868   n12->ReplaceInput(0, n8);
869   op = common_builder.Phi(kMachAnyTagged, 2);
870   Node* n9 = graph.NewNode(op, nil, nil, nil);
871   USE(n9);
872   op = common_builder.Parameter(0);
873   Node* n3 = graph.NewNode(op, n0);
874   USE(n3);
875   n9->ReplaceInput(0, n3);
876   n9->ReplaceInput(1, n9);
877   op = common_builder.Loop(2);
878   Node* n6 = graph.NewNode(op, nil, nil);
879   USE(n6);
880   n6->ReplaceInput(0, n0);
881   op = common_builder.IfTrue();
882   Node* n14 = graph.NewNode(op, nil);
883   USE(n14);
884   op = common_builder.Branch();
885   Node* n13 = graph.NewNode(op, nil, nil);
886   USE(n13);
887   n13->ReplaceInput(0, n12);
888   n13->ReplaceInput(1, n6);
889   n14->ReplaceInput(0, n13);
890   n6->ReplaceInput(1, n14);
891   n9->ReplaceInput(2, n6);
892   n12->ReplaceInput(1, n9);
893   n12->ReplaceInput(2, n5);
894   op = common_builder.Phi(kMachAnyTagged, 2);
895   Node* n10 = graph.NewNode(op, nil, nil, nil);
896   USE(n10);
897   n10->ReplaceInput(0, n0);
898   n10->ReplaceInput(1, n18);
899   n10->ReplaceInput(2, n6);
900   n12->ReplaceInput(3, n10);
901   n12->ReplaceInput(4, n6);
902   n16->ReplaceInput(2, n12);
903   n16->ReplaceInput(3, n14);
904   n18->ReplaceInput(0, n16);
905   op = common_builder.NumberConstant(0);
906   Node* n17 = graph.NewNode(op);
907   USE(n17);
908   n18->ReplaceInput(1, n17);
909   n18->ReplaceInput(2, n5);
910   n18->ReplaceInput(3, n16);
911   n18->ReplaceInput(4, n14);
912   n8->ReplaceInput(1, n18);
913   n8->ReplaceInput(2, n6);
914   n19->ReplaceInput(0, n8);
915   n19->ReplaceInput(1, n12);
916   op = common_builder.IfFalse();
917   Node* n15 = graph.NewNode(op, nil);
918   USE(n15);
919   n15->ReplaceInput(0, n13);
920   n19->ReplaceInput(2, n15);
921   n20->ReplaceInput(0, n19);
922 
923   graph.SetStart(n0);
924   graph.SetEnd(n20);
925 
926   ComputeAndVerifySchedule(19, &graph);
927 }
928 
929 
TEST(BuildScheduleComplexLoops)930 TEST(BuildScheduleComplexLoops) {
931   HandleAndZoneScope scope;
932   Isolate* isolate = scope.main_isolate();
933   Graph graph(scope.main_zone());
934   CommonOperatorBuilder common_builder(scope.main_zone());
935   JSOperatorBuilder js_builder(scope.main_zone());
936   const Operator* op;
937 
938   Handle<Object> object =
939       Handle<Object>(isolate->heap()->undefined_value(), isolate);
940   Unique<Object> unique_constant = Unique<Object>::CreateUninitialized(object);
941 
942   // Manually transcripted code for:
943   // function turbo_fan_test(a, b, c) {
944   //   while (a < b) {
945   //     a++;
946   //     while (c < b) {
947   //       c++;
948   //     }
949   //   }
950   //   while (a < b) {
951   //     a += 2;
952   //   }
953   //   return a;
954   // }
955   op = common_builder.Start(0);
956   Node* n0 = graph.NewNode(op);
957   USE(n0);
958   Node* nil = graph.NewNode(common_builder.Dead());
959   op = common_builder.End();
960   Node* n46 = graph.NewNode(op, nil);
961   USE(n46);
962   op = common_builder.Return();
963   Node* n45 = graph.NewNode(op, nil, nil, nil);
964   USE(n45);
965   op = common_builder.Phi(kMachAnyTagged, 2);
966   Node* n35 = graph.NewNode(op, nil, nil, nil);
967   USE(n35);
968   op = common_builder.Phi(kMachAnyTagged, 2);
969   Node* n9 = graph.NewNode(op, nil, nil, nil);
970   USE(n9);
971   op = common_builder.Parameter(0);
972   Node* n2 = graph.NewNode(op, n0);
973   USE(n2);
974   n9->ReplaceInput(0, n2);
975   op = common_builder.Phi(kMachAnyTagged, 2);
976   Node* n23 = graph.NewNode(op, nil, nil, nil);
977   USE(n23);
978   op = js_builder.Add();
979   Node* n20 = graph.NewNode(op, nil, nil, nil, nil, nil);
980   USE(n20);
981   op = js_builder.ToNumber();
982   Node* n18 = graph.NewNode(op, nil, nil, nil, nil);
983   USE(n18);
984   n18->ReplaceInput(0, n9);
985   op = common_builder.HeapConstant(unique_constant);
986   Node* n6 = graph.NewNode(op);
987   USE(n6);
988   n18->ReplaceInput(1, n6);
989   op = js_builder.LessThan();
990   Node* n14 = graph.NewNode(op, nil, nil, nil, nil, nil);
991   USE(n14);
992   n14->ReplaceInput(0, n9);
993   op = common_builder.Phi(kMachAnyTagged, 2);
994   Node* n10 = graph.NewNode(op, nil, nil, nil);
995   USE(n10);
996   op = common_builder.Parameter(0);
997   Node* n3 = graph.NewNode(op, n0);
998   USE(n3);
999   n10->ReplaceInput(0, n3);
1000   op = common_builder.Phi(kMachAnyTagged, 2);
1001   Node* n24 = graph.NewNode(op, nil, nil, nil);
1002   USE(n24);
1003   n24->ReplaceInput(0, n10);
1004   n24->ReplaceInput(1, n24);
1005   op = common_builder.Loop(2);
1006   Node* n21 = graph.NewNode(op, nil, nil);
1007   USE(n21);
1008   op = common_builder.IfTrue();
1009   Node* n16 = graph.NewNode(op, nil);
1010   USE(n16);
1011   op = common_builder.Branch();
1012   Node* n15 = graph.NewNode(op, nil, nil);
1013   USE(n15);
1014   n15->ReplaceInput(0, n14);
1015   op = common_builder.Loop(2);
1016   Node* n7 = graph.NewNode(op, nil, nil);
1017   USE(n7);
1018   n7->ReplaceInput(0, n0);
1019   op = common_builder.IfFalse();
1020   Node* n30 = graph.NewNode(op, nil);
1021   USE(n30);
1022   op = common_builder.Branch();
1023   Node* n28 = graph.NewNode(op, nil, nil);
1024   USE(n28);
1025   op = js_builder.LessThan();
1026   Node* n27 = graph.NewNode(op, nil, nil, nil, nil, nil);
1027   USE(n27);
1028   op = common_builder.Phi(kMachAnyTagged, 2);
1029   Node* n25 = graph.NewNode(op, nil, nil, nil);
1030   USE(n25);
1031   op = common_builder.Phi(kMachAnyTagged, 2);
1032   Node* n11 = graph.NewNode(op, nil, nil, nil);
1033   USE(n11);
1034   op = common_builder.Parameter(0);
1035   Node* n4 = graph.NewNode(op, n0);
1036   USE(n4);
1037   n11->ReplaceInput(0, n4);
1038   n11->ReplaceInput(1, n25);
1039   n11->ReplaceInput(2, n7);
1040   n25->ReplaceInput(0, n11);
1041   op = js_builder.Add();
1042   Node* n32 = graph.NewNode(op, nil, nil, nil, nil, nil);
1043   USE(n32);
1044   op = js_builder.ToNumber();
1045   Node* n31 = graph.NewNode(op, nil, nil, nil, nil);
1046   USE(n31);
1047   n31->ReplaceInput(0, n25);
1048   n31->ReplaceInput(1, n6);
1049   n31->ReplaceInput(2, n27);
1050   op = common_builder.IfTrue();
1051   Node* n29 = graph.NewNode(op, nil);
1052   USE(n29);
1053   n29->ReplaceInput(0, n28);
1054   n31->ReplaceInput(3, n29);
1055   n32->ReplaceInput(0, n31);
1056   op = common_builder.NumberConstant(0);
1057   Node* n19 = graph.NewNode(op);
1058   USE(n19);
1059   n32->ReplaceInput(1, n19);
1060   n32->ReplaceInput(2, n6);
1061   n32->ReplaceInput(3, n31);
1062   n32->ReplaceInput(4, n29);
1063   n25->ReplaceInput(1, n32);
1064   n25->ReplaceInput(2, n21);
1065   n27->ReplaceInput(0, n25);
1066   n27->ReplaceInput(1, n24);
1067   n27->ReplaceInput(2, n6);
1068   op = common_builder.Phi(kMachAnyTagged, 2);
1069   Node* n26 = graph.NewNode(op, nil, nil, nil);
1070   USE(n26);
1071   n26->ReplaceInput(0, n20);
1072   n26->ReplaceInput(1, n32);
1073   n26->ReplaceInput(2, n21);
1074   n27->ReplaceInput(3, n26);
1075   n27->ReplaceInput(4, n21);
1076   n28->ReplaceInput(0, n27);
1077   n28->ReplaceInput(1, n21);
1078   n30->ReplaceInput(0, n28);
1079   n7->ReplaceInput(1, n30);
1080   n15->ReplaceInput(1, n7);
1081   n16->ReplaceInput(0, n15);
1082   n21->ReplaceInput(0, n16);
1083   n21->ReplaceInput(1, n29);
1084   n24->ReplaceInput(2, n21);
1085   n10->ReplaceInput(1, n24);
1086   n10->ReplaceInput(2, n7);
1087   n14->ReplaceInput(1, n10);
1088   n14->ReplaceInput(2, n6);
1089   op = common_builder.Phi(kMachAnyTagged, 2);
1090   Node* n12 = graph.NewNode(op, nil, nil, nil);
1091   USE(n12);
1092   n12->ReplaceInput(0, n0);
1093   n12->ReplaceInput(1, n27);
1094   n12->ReplaceInput(2, n7);
1095   n14->ReplaceInput(3, n12);
1096   n14->ReplaceInput(4, n7);
1097   n18->ReplaceInput(2, n14);
1098   n18->ReplaceInput(3, n16);
1099   n20->ReplaceInput(0, n18);
1100   n20->ReplaceInput(1, n19);
1101   n20->ReplaceInput(2, n6);
1102   n20->ReplaceInput(3, n18);
1103   n20->ReplaceInput(4, n16);
1104   n23->ReplaceInput(0, n20);
1105   n23->ReplaceInput(1, n23);
1106   n23->ReplaceInput(2, n21);
1107   n9->ReplaceInput(1, n23);
1108   n9->ReplaceInput(2, n7);
1109   n35->ReplaceInput(0, n9);
1110   op = js_builder.Add();
1111   Node* n44 = graph.NewNode(op, nil, nil, nil, nil, nil);
1112   USE(n44);
1113   n44->ReplaceInput(0, n35);
1114   op = common_builder.NumberConstant(0);
1115   Node* n43 = graph.NewNode(op);
1116   USE(n43);
1117   n44->ReplaceInput(1, n43);
1118   n44->ReplaceInput(2, n6);
1119   op = js_builder.LessThan();
1120   Node* n39 = graph.NewNode(op, nil, nil, nil, nil, nil);
1121   USE(n39);
1122   n39->ReplaceInput(0, n35);
1123   op = common_builder.Phi(kMachAnyTagged, 2);
1124   Node* n36 = graph.NewNode(op, nil, nil, nil);
1125   USE(n36);
1126   n36->ReplaceInput(0, n10);
1127   n36->ReplaceInput(1, n36);
1128   op = common_builder.Loop(2);
1129   Node* n33 = graph.NewNode(op, nil, nil);
1130   USE(n33);
1131   op = common_builder.IfFalse();
1132   Node* n17 = graph.NewNode(op, nil);
1133   USE(n17);
1134   n17->ReplaceInput(0, n15);
1135   n33->ReplaceInput(0, n17);
1136   op = common_builder.IfTrue();
1137   Node* n41 = graph.NewNode(op, nil);
1138   USE(n41);
1139   op = common_builder.Branch();
1140   Node* n40 = graph.NewNode(op, nil, nil);
1141   USE(n40);
1142   n40->ReplaceInput(0, n39);
1143   n40->ReplaceInput(1, n33);
1144   n41->ReplaceInput(0, n40);
1145   n33->ReplaceInput(1, n41);
1146   n36->ReplaceInput(2, n33);
1147   n39->ReplaceInput(1, n36);
1148   n39->ReplaceInput(2, n6);
1149   op = common_builder.Phi(kMachAnyTagged, 2);
1150   Node* n38 = graph.NewNode(op, nil, nil, nil);
1151   USE(n38);
1152   n38->ReplaceInput(0, n14);
1153   n38->ReplaceInput(1, n44);
1154   n38->ReplaceInput(2, n33);
1155   n39->ReplaceInput(3, n38);
1156   n39->ReplaceInput(4, n33);
1157   n44->ReplaceInput(3, n39);
1158   n44->ReplaceInput(4, n41);
1159   n35->ReplaceInput(1, n44);
1160   n35->ReplaceInput(2, n33);
1161   n45->ReplaceInput(0, n35);
1162   n45->ReplaceInput(1, n39);
1163   op = common_builder.IfFalse();
1164   Node* n42 = graph.NewNode(op, nil);
1165   USE(n42);
1166   n42->ReplaceInput(0, n40);
1167   n45->ReplaceInput(2, n42);
1168   n46->ReplaceInput(0, n45);
1169 
1170   graph.SetStart(n0);
1171   graph.SetEnd(n46);
1172 
1173   ComputeAndVerifySchedule(46, &graph);
1174 }
1175 
1176 
TEST(BuildScheduleBreakAndContinue)1177 TEST(BuildScheduleBreakAndContinue) {
1178   HandleAndZoneScope scope;
1179   Isolate* isolate = scope.main_isolate();
1180   Graph graph(scope.main_zone());
1181   CommonOperatorBuilder common_builder(scope.main_zone());
1182   JSOperatorBuilder js_builder(scope.main_zone());
1183   const Operator* op;
1184 
1185   Handle<Object> object =
1186       Handle<Object>(isolate->heap()->undefined_value(), isolate);
1187   Unique<Object> unique_constant = Unique<Object>::CreateUninitialized(object);
1188 
1189   // Manually transcripted code for:
1190   // function turbo_fan_test(a, b, c) {
1191   //   var d = 0;
1192   //   while (a < b) {
1193   //     a++;
1194   //     while (c < b) {
1195   //       c++;
1196   //       if (d == 0) break;
1197   //       a++;
1198   //     }
1199   //     if (a == 1) continue;
1200   //     d++;
1201   //   }
1202   //   return a + d;
1203   // }
1204   op = common_builder.Start(0);
1205   Node* n0 = graph.NewNode(op);
1206   USE(n0);
1207   Node* nil = graph.NewNode(common_builder.Dead());
1208   op = common_builder.End();
1209   Node* n58 = graph.NewNode(op, nil);
1210   USE(n58);
1211   op = common_builder.Return();
1212   Node* n57 = graph.NewNode(op, nil, nil, nil);
1213   USE(n57);
1214   op = js_builder.Add();
1215   Node* n56 = graph.NewNode(op, nil, nil, nil, nil, nil);
1216   USE(n56);
1217   op = common_builder.Phi(kMachAnyTagged, 2);
1218   Node* n10 = graph.NewNode(op, nil, nil, nil);
1219   USE(n10);
1220   op = common_builder.Parameter(0);
1221   Node* n2 = graph.NewNode(op, n0);
1222   USE(n2);
1223   n10->ReplaceInput(0, n2);
1224   op = common_builder.Phi(kMachAnyTagged, 2);
1225   Node* n25 = graph.NewNode(op, nil, nil, nil);
1226   USE(n25);
1227   op = js_builder.Add();
1228   Node* n22 = graph.NewNode(op, nil, nil, nil, nil, nil);
1229   USE(n22);
1230   op = js_builder.ToNumber();
1231   Node* n20 = graph.NewNode(op, nil, nil, nil, nil);
1232   USE(n20);
1233   n20->ReplaceInput(0, n10);
1234   op = common_builder.HeapConstant(unique_constant);
1235   Node* n6 = graph.NewNode(op);
1236   USE(n6);
1237   n20->ReplaceInput(1, n6);
1238   op = js_builder.LessThan();
1239   Node* n16 = graph.NewNode(op, nil, nil, nil, nil, nil);
1240   USE(n16);
1241   n16->ReplaceInput(0, n10);
1242   op = common_builder.Phi(kMachAnyTagged, 2);
1243   Node* n11 = graph.NewNode(op, nil, nil, nil);
1244   USE(n11);
1245   op = common_builder.Parameter(0);
1246   Node* n3 = graph.NewNode(op, n0);
1247   USE(n3);
1248   n11->ReplaceInput(0, n3);
1249   op = common_builder.Phi(kMachAnyTagged, 2);
1250   Node* n26 = graph.NewNode(op, nil, nil, nil);
1251   USE(n26);
1252   n26->ReplaceInput(0, n11);
1253   n26->ReplaceInput(1, n26);
1254   op = common_builder.Loop(2);
1255   Node* n23 = graph.NewNode(op, nil, nil);
1256   USE(n23);
1257   op = common_builder.IfTrue();
1258   Node* n18 = graph.NewNode(op, nil);
1259   USE(n18);
1260   op = common_builder.Branch();
1261   Node* n17 = graph.NewNode(op, nil, nil);
1262   USE(n17);
1263   n17->ReplaceInput(0, n16);
1264   op = common_builder.Loop(2);
1265   Node* n8 = graph.NewNode(op, nil, nil);
1266   USE(n8);
1267   n8->ReplaceInput(0, n0);
1268   op = common_builder.Merge(2);
1269   Node* n53 = graph.NewNode(op, nil, nil);
1270   USE(n53);
1271   op = common_builder.IfTrue();
1272   Node* n49 = graph.NewNode(op, nil);
1273   USE(n49);
1274   op = common_builder.Branch();
1275   Node* n48 = graph.NewNode(op, nil, nil);
1276   USE(n48);
1277   op = js_builder.Equal();
1278   Node* n47 = graph.NewNode(op, nil, nil, nil, nil, nil);
1279   USE(n47);
1280   n47->ReplaceInput(0, n25);
1281   op = common_builder.NumberConstant(0);
1282   Node* n46 = graph.NewNode(op);
1283   USE(n46);
1284   n47->ReplaceInput(1, n46);
1285   n47->ReplaceInput(2, n6);
1286   op = common_builder.Phi(kMachAnyTagged, 2);
1287   Node* n42 = graph.NewNode(op, nil, nil, nil);
1288   USE(n42);
1289   op = js_builder.LessThan();
1290   Node* n30 = graph.NewNode(op, nil, nil, nil, nil, nil);
1291   USE(n30);
1292   op = common_builder.Phi(kMachAnyTagged, 2);
1293   Node* n27 = graph.NewNode(op, nil, nil, nil);
1294   USE(n27);
1295   op = common_builder.Phi(kMachAnyTagged, 2);
1296   Node* n12 = graph.NewNode(op, nil, nil, nil);
1297   USE(n12);
1298   op = common_builder.Parameter(0);
1299   Node* n4 = graph.NewNode(op, n0);
1300   USE(n4);
1301   n12->ReplaceInput(0, n4);
1302   op = common_builder.Phi(kMachAnyTagged, 2);
1303   Node* n41 = graph.NewNode(op, nil, nil, nil);
1304   USE(n41);
1305   n41->ReplaceInput(0, n27);
1306   op = js_builder.Add();
1307   Node* n35 = graph.NewNode(op, nil, nil, nil, nil, nil);
1308   USE(n35);
1309   op = js_builder.ToNumber();
1310   Node* n34 = graph.NewNode(op, nil, nil, nil, nil);
1311   USE(n34);
1312   n34->ReplaceInput(0, n27);
1313   n34->ReplaceInput(1, n6);
1314   n34->ReplaceInput(2, n30);
1315   op = common_builder.IfTrue();
1316   Node* n32 = graph.NewNode(op, nil);
1317   USE(n32);
1318   op = common_builder.Branch();
1319   Node* n31 = graph.NewNode(op, nil, nil);
1320   USE(n31);
1321   n31->ReplaceInput(0, n30);
1322   n31->ReplaceInput(1, n23);
1323   n32->ReplaceInput(0, n31);
1324   n34->ReplaceInput(3, n32);
1325   n35->ReplaceInput(0, n34);
1326   op = common_builder.NumberConstant(0);
1327   Node* n21 = graph.NewNode(op);
1328   USE(n21);
1329   n35->ReplaceInput(1, n21);
1330   n35->ReplaceInput(2, n6);
1331   n35->ReplaceInput(3, n34);
1332   n35->ReplaceInput(4, n32);
1333   n41->ReplaceInput(1, n35);
1334   op = common_builder.Merge(2);
1335   Node* n40 = graph.NewNode(op, nil, nil);
1336   USE(n40);
1337   op = common_builder.IfFalse();
1338   Node* n33 = graph.NewNode(op, nil);
1339   USE(n33);
1340   n33->ReplaceInput(0, n31);
1341   n40->ReplaceInput(0, n33);
1342   op = common_builder.IfTrue();
1343   Node* n39 = graph.NewNode(op, nil);
1344   USE(n39);
1345   op = common_builder.Branch();
1346   Node* n38 = graph.NewNode(op, nil, nil);
1347   USE(n38);
1348   op = js_builder.Equal();
1349   Node* n37 = graph.NewNode(op, nil, nil, nil, nil, nil);
1350   USE(n37);
1351   op = common_builder.Phi(kMachAnyTagged, 2);
1352   Node* n28 = graph.NewNode(op, nil, nil, nil);
1353   USE(n28);
1354   op = common_builder.Phi(kMachAnyTagged, 2);
1355   Node* n13 = graph.NewNode(op, nil, nil, nil);
1356   USE(n13);
1357   op = common_builder.NumberConstant(0);
1358   Node* n7 = graph.NewNode(op);
1359   USE(n7);
1360   n13->ReplaceInput(0, n7);
1361   op = common_builder.Phi(kMachAnyTagged, 2);
1362   Node* n54 = graph.NewNode(op, nil, nil, nil);
1363   USE(n54);
1364   n54->ReplaceInput(0, n28);
1365   op = js_builder.Add();
1366   Node* n52 = graph.NewNode(op, nil, nil, nil, nil, nil);
1367   USE(n52);
1368   op = js_builder.ToNumber();
1369   Node* n51 = graph.NewNode(op, nil, nil, nil, nil);
1370   USE(n51);
1371   n51->ReplaceInput(0, n28);
1372   n51->ReplaceInput(1, n6);
1373   n51->ReplaceInput(2, n47);
1374   op = common_builder.IfFalse();
1375   Node* n50 = graph.NewNode(op, nil);
1376   USE(n50);
1377   n50->ReplaceInput(0, n48);
1378   n51->ReplaceInput(3, n50);
1379   n52->ReplaceInput(0, n51);
1380   n52->ReplaceInput(1, n21);
1381   n52->ReplaceInput(2, n6);
1382   n52->ReplaceInput(3, n51);
1383   n52->ReplaceInput(4, n50);
1384   n54->ReplaceInput(1, n52);
1385   n54->ReplaceInput(2, n53);
1386   n13->ReplaceInput(1, n54);
1387   n13->ReplaceInput(2, n8);
1388   n28->ReplaceInput(0, n13);
1389   n28->ReplaceInput(1, n28);
1390   n28->ReplaceInput(2, n23);
1391   n37->ReplaceInput(0, n28);
1392   op = common_builder.NumberConstant(0);
1393   Node* n36 = graph.NewNode(op);
1394   USE(n36);
1395   n37->ReplaceInput(1, n36);
1396   n37->ReplaceInput(2, n6);
1397   n37->ReplaceInput(3, n35);
1398   n37->ReplaceInput(4, n32);
1399   n38->ReplaceInput(0, n37);
1400   n38->ReplaceInput(1, n32);
1401   n39->ReplaceInput(0, n38);
1402   n40->ReplaceInput(1, n39);
1403   n41->ReplaceInput(2, n40);
1404   n12->ReplaceInput(1, n41);
1405   n12->ReplaceInput(2, n8);
1406   n27->ReplaceInput(0, n12);
1407   n27->ReplaceInput(1, n35);
1408   n27->ReplaceInput(2, n23);
1409   n30->ReplaceInput(0, n27);
1410   n30->ReplaceInput(1, n26);
1411   n30->ReplaceInput(2, n6);
1412   op = common_builder.Phi(kMachAnyTagged, 2);
1413   Node* n29 = graph.NewNode(op, nil, nil, nil);
1414   USE(n29);
1415   n29->ReplaceInput(0, n22);
1416   op = js_builder.Add();
1417   Node* n45 = graph.NewNode(op, nil, nil, nil, nil, nil);
1418   USE(n45);
1419   op = js_builder.ToNumber();
1420   Node* n44 = graph.NewNode(op, nil, nil, nil, nil);
1421   USE(n44);
1422   n44->ReplaceInput(0, n25);
1423   n44->ReplaceInput(1, n6);
1424   n44->ReplaceInput(2, n37);
1425   op = common_builder.IfFalse();
1426   Node* n43 = graph.NewNode(op, nil);
1427   USE(n43);
1428   n43->ReplaceInput(0, n38);
1429   n44->ReplaceInput(3, n43);
1430   n45->ReplaceInput(0, n44);
1431   n45->ReplaceInput(1, n21);
1432   n45->ReplaceInput(2, n6);
1433   n45->ReplaceInput(3, n44);
1434   n45->ReplaceInput(4, n43);
1435   n29->ReplaceInput(1, n45);
1436   n29->ReplaceInput(2, n23);
1437   n30->ReplaceInput(3, n29);
1438   n30->ReplaceInput(4, n23);
1439   n42->ReplaceInput(0, n30);
1440   n42->ReplaceInput(1, n37);
1441   n42->ReplaceInput(2, n40);
1442   n47->ReplaceInput(3, n42);
1443   n47->ReplaceInput(4, n40);
1444   n48->ReplaceInput(0, n47);
1445   n48->ReplaceInput(1, n40);
1446   n49->ReplaceInput(0, n48);
1447   n53->ReplaceInput(0, n49);
1448   n53->ReplaceInput(1, n50);
1449   n8->ReplaceInput(1, n53);
1450   n17->ReplaceInput(1, n8);
1451   n18->ReplaceInput(0, n17);
1452   n23->ReplaceInput(0, n18);
1453   n23->ReplaceInput(1, n43);
1454   n26->ReplaceInput(2, n23);
1455   n11->ReplaceInput(1, n26);
1456   n11->ReplaceInput(2, n8);
1457   n16->ReplaceInput(1, n11);
1458   n16->ReplaceInput(2, n6);
1459   op = common_builder.Phi(kMachAnyTagged, 2);
1460   Node* n14 = graph.NewNode(op, nil, nil, nil);
1461   USE(n14);
1462   n14->ReplaceInput(0, n0);
1463   op = common_builder.Phi(kMachAnyTagged, 2);
1464   Node* n55 = graph.NewNode(op, nil, nil, nil);
1465   USE(n55);
1466   n55->ReplaceInput(0, n47);
1467   n55->ReplaceInput(1, n52);
1468   n55->ReplaceInput(2, n53);
1469   n14->ReplaceInput(1, n55);
1470   n14->ReplaceInput(2, n8);
1471   n16->ReplaceInput(3, n14);
1472   n16->ReplaceInput(4, n8);
1473   n20->ReplaceInput(2, n16);
1474   n20->ReplaceInput(3, n18);
1475   n22->ReplaceInput(0, n20);
1476   n22->ReplaceInput(1, n21);
1477   n22->ReplaceInput(2, n6);
1478   n22->ReplaceInput(3, n20);
1479   n22->ReplaceInput(4, n18);
1480   n25->ReplaceInput(0, n22);
1481   n25->ReplaceInput(1, n45);
1482   n25->ReplaceInput(2, n23);
1483   n10->ReplaceInput(1, n25);
1484   n10->ReplaceInput(2, n8);
1485   n56->ReplaceInput(0, n10);
1486   n56->ReplaceInput(1, n13);
1487   n56->ReplaceInput(2, n6);
1488   n56->ReplaceInput(3, n16);
1489   op = common_builder.IfFalse();
1490   Node* n19 = graph.NewNode(op, nil);
1491   USE(n19);
1492   n19->ReplaceInput(0, n17);
1493   n56->ReplaceInput(4, n19);
1494   n57->ReplaceInput(0, n56);
1495   n57->ReplaceInput(1, n56);
1496   n57->ReplaceInput(2, n19);
1497   n58->ReplaceInput(0, n57);
1498 
1499   graph.SetStart(n0);
1500   graph.SetEnd(n58);
1501 
1502   ComputeAndVerifySchedule(62, &graph);
1503 }
1504 
1505 
TEST(BuildScheduleSimpleLoopWithCodeMotion)1506 TEST(BuildScheduleSimpleLoopWithCodeMotion) {
1507   HandleAndZoneScope scope;
1508   Isolate* isolate = scope.main_isolate();
1509   Graph graph(scope.main_zone());
1510   CommonOperatorBuilder common_builder(scope.main_zone());
1511   JSOperatorBuilder js_builder(scope.main_zone());
1512   MachineOperatorBuilder machine_builder;
1513   const Operator* op;
1514 
1515   Handle<Object> object =
1516       Handle<Object>(isolate->heap()->undefined_value(), isolate);
1517   Unique<Object> unique_constant = Unique<Object>::CreateUninitialized(object);
1518 
1519   // Manually transcripted code for:
1520   // function turbo_fan_test(a, b, c) {
1521   //   while (a < b) {
1522   //     a += b + c;
1523   //   }
1524   //   return a;
1525   // }
1526   op = common_builder.Start(0);
1527   Node* n0 = graph.NewNode(op);
1528   USE(n0);
1529   Node* nil = graph.NewNode(common_builder.Dead());
1530   op = common_builder.End();
1531   Node* n22 = graph.NewNode(op, nil);
1532   USE(n22);
1533   op = common_builder.Return();
1534   Node* n21 = graph.NewNode(op, nil, nil, nil);
1535   USE(n21);
1536   op = common_builder.Phi(kMachAnyTagged, 2);
1537   Node* n9 = graph.NewNode(op, nil, nil, nil);
1538   USE(n9);
1539   op = common_builder.Parameter(0);
1540   Node* n2 = graph.NewNode(op, n0);
1541   USE(n2);
1542   n9->ReplaceInput(0, n2);
1543   op = js_builder.Add();
1544   Node* n20 = graph.NewNode(op, nil, nil, nil, nil, nil);
1545   USE(n20);
1546   n20->ReplaceInput(0, n9);
1547   op = machine_builder.Int32Add();
1548   Node* n19 = graph.NewNode(op, nil, nil);
1549   USE(n19);
1550   op = common_builder.Phi(kMachAnyTagged, 2);
1551   Node* n10 = graph.NewNode(op, nil, nil, nil);
1552   USE(n10);
1553   op = common_builder.Parameter(0);
1554   Node* n3 = graph.NewNode(op, n0);
1555   USE(n3);
1556   n10->ReplaceInput(0, n3);
1557   n10->ReplaceInput(1, n10);
1558   op = common_builder.Loop(2);
1559   Node* n7 = graph.NewNode(op, nil, nil);
1560   USE(n7);
1561   n7->ReplaceInput(0, n0);
1562   op = common_builder.IfTrue();
1563   Node* n17 = graph.NewNode(op, nil);
1564   USE(n17);
1565   op = common_builder.Branch();
1566   Node* n16 = graph.NewNode(op, nil, nil);
1567   USE(n16);
1568   op = js_builder.ToBoolean();
1569   Node* n15 = graph.NewNode(op, nil, nil, nil, nil);
1570   USE(n15);
1571   op = js_builder.LessThan();
1572   Node* n14 = graph.NewNode(op, nil, nil, nil, nil, nil);
1573   USE(n14);
1574   n14->ReplaceInput(0, n9);
1575   n14->ReplaceInput(1, n10);
1576   op = common_builder.HeapConstant(unique_constant);
1577   Node* n6 = graph.NewNode(op);
1578   USE(n6);
1579   n14->ReplaceInput(2, n6);
1580   op = common_builder.Phi(kMachAnyTagged, 2);
1581   Node* n12 = graph.NewNode(op, nil, nil, nil);
1582   USE(n12);
1583   n12->ReplaceInput(0, n0);
1584   n12->ReplaceInput(1, n20);
1585   n12->ReplaceInput(2, n7);
1586   n14->ReplaceInput(3, n12);
1587   n14->ReplaceInput(4, n7);
1588   n15->ReplaceInput(0, n14);
1589   n15->ReplaceInput(1, n6);
1590   n15->ReplaceInput(2, n14);
1591   n15->ReplaceInput(3, n7);
1592   n16->ReplaceInput(0, n15);
1593   n16->ReplaceInput(1, n7);
1594   n17->ReplaceInput(0, n16);
1595   n7->ReplaceInput(1, n17);
1596   n10->ReplaceInput(2, n7);
1597   n19->ReplaceInput(0, n2);
1598   op = common_builder.Phi(kMachAnyTagged, 2);
1599   Node* n11 = graph.NewNode(op, nil, nil, nil);
1600   USE(n11);
1601   op = common_builder.Parameter(0);
1602   Node* n4 = graph.NewNode(op, n0);
1603   USE(n4);
1604   n11->ReplaceInput(0, n4);
1605   n11->ReplaceInput(1, n11);
1606   n11->ReplaceInput(2, n7);
1607   n19->ReplaceInput(1, n3);
1608   n20->ReplaceInput(1, n19);
1609   n20->ReplaceInput(2, n6);
1610   n20->ReplaceInput(3, n19);
1611   n20->ReplaceInput(4, n17);
1612   n9->ReplaceInput(1, n20);
1613   n9->ReplaceInput(2, n7);
1614   n21->ReplaceInput(0, n9);
1615   n21->ReplaceInput(1, n15);
1616   op = common_builder.IfFalse();
1617   Node* n18 = graph.NewNode(op, nil);
1618   USE(n18);
1619   n18->ReplaceInput(0, n16);
1620   n21->ReplaceInput(2, n18);
1621   n22->ReplaceInput(0, n21);
1622 
1623   graph.SetStart(n0);
1624   graph.SetEnd(n22);
1625 
1626   Schedule* schedule = ComputeAndVerifySchedule(19, &graph);
1627   // Make sure the integer-only add gets hoisted to a different block that the
1628   // JSAdd.
1629   CHECK(schedule->block(n19) != schedule->block(n20));
1630 }
1631 
1632 
1633 #if V8_TURBOFAN_TARGET
1634 
CreateDiamond(Graph * graph,CommonOperatorBuilder * common,Node * cond)1635 static Node* CreateDiamond(Graph* graph, CommonOperatorBuilder* common,
1636                            Node* cond) {
1637   Node* tv = graph->NewNode(common->Int32Constant(6));
1638   Node* fv = graph->NewNode(common->Int32Constant(7));
1639   Node* br = graph->NewNode(common->Branch(), cond, graph->start());
1640   Node* t = graph->NewNode(common->IfTrue(), br);
1641   Node* f = graph->NewNode(common->IfFalse(), br);
1642   Node* m = graph->NewNode(common->Merge(2), t, f);
1643   Node* phi = graph->NewNode(common->Phi(kMachAnyTagged, 2), tv, fv, m);
1644   return phi;
1645 }
1646 
1647 
TEST(FloatingDiamond1)1648 TEST(FloatingDiamond1) {
1649   HandleAndZoneScope scope;
1650   Graph graph(scope.main_zone());
1651   CommonOperatorBuilder common(scope.main_zone());
1652 
1653   Node* start = graph.NewNode(common.Start(1));
1654   graph.SetStart(start);
1655 
1656   Node* p0 = graph.NewNode(common.Parameter(0), start);
1657   Node* d1 = CreateDiamond(&graph, &common, p0);
1658   Node* ret = graph.NewNode(common.Return(), d1, start, start);
1659   Node* end = graph.NewNode(common.End(), ret, start);
1660 
1661   graph.SetEnd(end);
1662 
1663   ComputeAndVerifySchedule(13, &graph);
1664 }
1665 
1666 
TEST(FloatingDiamond2)1667 TEST(FloatingDiamond2) {
1668   HandleAndZoneScope scope;
1669   Graph graph(scope.main_zone());
1670   CommonOperatorBuilder common(scope.main_zone());
1671   MachineOperatorBuilder machine;
1672 
1673   Node* start = graph.NewNode(common.Start(2));
1674   graph.SetStart(start);
1675 
1676   Node* p0 = graph.NewNode(common.Parameter(0), start);
1677   Node* p1 = graph.NewNode(common.Parameter(1), start);
1678   Node* d1 = CreateDiamond(&graph, &common, p0);
1679   Node* d2 = CreateDiamond(&graph, &common, p1);
1680   Node* add = graph.NewNode(machine.Int32Add(), d1, d2);
1681   Node* ret = graph.NewNode(common.Return(), add, start, start);
1682   Node* end = graph.NewNode(common.End(), ret, start);
1683 
1684   graph.SetEnd(end);
1685 
1686   ComputeAndVerifySchedule(24, &graph);
1687 }
1688 
1689 
TEST(FloatingDiamond3)1690 TEST(FloatingDiamond3) {
1691   HandleAndZoneScope scope;
1692   Graph graph(scope.main_zone());
1693   CommonOperatorBuilder common(scope.main_zone());
1694   MachineOperatorBuilder machine;
1695 
1696   Node* start = graph.NewNode(common.Start(2));
1697   graph.SetStart(start);
1698 
1699   Node* p0 = graph.NewNode(common.Parameter(0), start);
1700   Node* p1 = graph.NewNode(common.Parameter(1), start);
1701   Node* d1 = CreateDiamond(&graph, &common, p0);
1702   Node* d2 = CreateDiamond(&graph, &common, p1);
1703   Node* add = graph.NewNode(machine.Int32Add(), d1, d2);
1704   Node* d3 = CreateDiamond(&graph, &common, add);
1705   Node* ret = graph.NewNode(common.Return(), d3, start, start);
1706   Node* end = graph.NewNode(common.End(), ret, start);
1707 
1708   graph.SetEnd(end);
1709 
1710   ComputeAndVerifySchedule(33, &graph);
1711 }
1712 
1713 #endif
1714