Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(288)

Side by Side Diff: test/cctest/compiler/test-scheduler.cc

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

Powered by Google App Engine
This is Rietveld 408576698