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
21using namespace v8::internal;
22using namespace v8::internal::compiler;
23
24// TODO(titzer): pull RPO tests out to their own file.
25struct TestLoop {
26  int count;
27  BasicBlock** nodes;
28  BasicBlock* header() { return nodes[0]; }
29  BasicBlock* last() { return nodes[count - 1]; }
30  ~TestLoop() { delete[] nodes; }
31};
32
33
34static 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
47static 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
57static 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
70static 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
88static 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
106TEST(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
116TEST(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
128TEST(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
155TEST(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
166TEST(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
178TEST(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
189TEST(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
201TEST(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
225TEST(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
246TEST(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
267TEST(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
310TEST(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
339TEST(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
377TEST(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
401TEST(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
427TEST(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
452TEST(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
484TEST(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
509TEST(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
536TEST(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
562TEST(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
594TEST(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
620TEST(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
631TEST(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
646TEST(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
673TEST(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
818TEST(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
930TEST(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
1177TEST(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
1506TEST(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
1635static 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
1648TEST(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
1667TEST(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
1690TEST(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