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

Issues Search
    My Issues | Starred     Open | Closed | All

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

Issue 863213003: Convert compiler cctest to unittests: SchedulerTest (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: More cleanup Created 5 years, 11 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
« no previous file with comments | « test/cctest/cctest.gyp ('k') | test/unittests/compiler/scheduler-unittest.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
7 #include "src/compiler/access-builder.h"
8 #include "src/compiler/common-operator.h"
9 #include "src/compiler/graph.h"
10 #include "src/compiler/graph-visualizer.h"
11 #include "src/compiler/js-operator.h"
12 #include "src/compiler/node.h"
13 #include "src/compiler/opcodes.h"
14 #include "src/compiler/operator.h"
15 #include "src/compiler/schedule.h"
16 #include "src/compiler/scheduler.h"
17 #include "src/compiler/simplified-operator.h"
18 #include "src/compiler/verifier.h"
19 #include "test/cctest/cctest.h"
20
21 using namespace v8::internal;
22 using namespace v8::internal::compiler;
23
24 Operator kIntAdd(IrOpcode::kInt32Add, Operator::kPure, "Int32Add", 2, 0, 0, 1,
25 0, 0);
26
27 // TODO(titzer): pull RPO tests out to their own file.
28 static void CheckRPONumbers(BasicBlockVector* order, size_t expected,
29 bool loops_allowed) {
30 CHECK(expected == order->size());
31 for (int i = 0; i < static_cast<int>(order->size()); i++) {
32 CHECK(order->at(i)->rpo_number() == i);
33 if (!loops_allowed) {
34 CHECK_EQ(NULL, order->at(i)->loop_end());
35 CHECK_EQ(NULL, order->at(i)->loop_header());
36 }
37 }
38 }
39
40
41 static void CheckLoop(BasicBlockVector* order, BasicBlock** blocks,
42 int body_size) {
43 BasicBlock* header = blocks[0];
44 BasicBlock* end = header->loop_end();
45 CHECK_NE(NULL, end);
46 CHECK_GT(end->rpo_number(), 0);
47 CHECK_EQ(body_size, end->rpo_number() - header->rpo_number());
48 for (int i = 0; i < body_size; i++) {
49 CHECK_GE(blocks[i]->rpo_number(), header->rpo_number());
50 CHECK_LT(blocks[i]->rpo_number(), end->rpo_number());
51 CHECK(header->LoopContains(blocks[i]));
52 CHECK(header->IsLoopHeader() || blocks[i]->loop_header() == header);
53 }
54 if (header->rpo_number() > 0) {
55 CHECK_NE(order->at(header->rpo_number() - 1)->loop_header(), header);
56 }
57 if (end->rpo_number() < static_cast<int>(order->size())) {
58 CHECK_NE(order->at(end->rpo_number())->loop_header(), header);
59 }
60 }
61
62
63 struct TestLoop {
64 int count;
65 BasicBlock** nodes;
66 BasicBlock* header() { return nodes[0]; }
67 BasicBlock* last() { return nodes[count - 1]; }
68 ~TestLoop() { delete[] nodes; }
69
70 void Check(BasicBlockVector* order) { CheckLoop(order, nodes, count); }
71 };
72
73
74 static TestLoop* CreateLoop(Schedule* schedule, int count) {
75 TestLoop* loop = new TestLoop();
76 loop->count = count;
77 loop->nodes = new BasicBlock* [count];
78 for (int i = 0; i < count; i++) {
79 loop->nodes[i] = schedule->NewBasicBlock();
80 if (i > 0) {
81 schedule->AddSuccessorForTesting(loop->nodes[i - 1], loop->nodes[i]);
82 }
83 }
84 schedule->AddSuccessorForTesting(loop->nodes[count - 1], loop->nodes[0]);
85 return loop;
86 }
87
88
89 static int GetScheduledNodeCount(const Schedule* schedule) {
90 size_t node_count = 0;
91 for (auto block : *schedule->rpo_order()) {
92 node_count += block->NodeCount();
93 if (block->control() != BasicBlock::kNone) ++node_count;
94 }
95 return static_cast<int>(node_count);
96 }
97
98
99 static Schedule* ComputeAndVerifySchedule(int expected, Graph* graph) {
100 if (FLAG_trace_turbo) {
101 OFStream os(stdout);
102 os << AsDOT(*graph);
103 }
104
105 Schedule* schedule = Scheduler::ComputeSchedule(graph->zone(), graph);
106
107 if (FLAG_trace_turbo_scheduler) {
108 OFStream os(stdout);
109 os << *schedule << std::endl;
110 }
111 ScheduleVerifier::Run(schedule);
112 CHECK_EQ(expected, GetScheduledNodeCount(schedule));
113 return schedule;
114 }
115
116
117 TEST(RPODegenerate1) {
118 HandleAndZoneScope scope;
119 Schedule schedule(scope.main_zone());
120
121 BasicBlockVector* order =
122 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
123 CheckRPONumbers(order, 1, false);
124 CHECK_EQ(schedule.start(), order->at(0));
125 }
126
127
128 TEST(RPODegenerate2) {
129 HandleAndZoneScope scope;
130 Schedule schedule(scope.main_zone());
131
132 schedule.AddGoto(schedule.start(), schedule.end());
133 BasicBlockVector* order =
134 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
135 CheckRPONumbers(order, 2, false);
136 CHECK_EQ(schedule.start(), order->at(0));
137 CHECK_EQ(schedule.end(), order->at(1));
138 }
139
140
141 TEST(RPOLine) {
142 HandleAndZoneScope scope;
143
144 for (int i = 0; i < 10; i++) {
145 Schedule schedule(scope.main_zone());
146
147 BasicBlock* last = schedule.start();
148 for (int j = 0; j < i; j++) {
149 BasicBlock* block = schedule.NewBasicBlock();
150 block->set_deferred(i & 1);
151 schedule.AddGoto(last, block);
152 last = block;
153 }
154 BasicBlockVector* order =
155 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
156 CheckRPONumbers(order, 1 + i, false);
157
158 for (size_t i = 0; i < schedule.BasicBlockCount(); i++) {
159 BasicBlock* block = schedule.GetBlockById(BasicBlock::Id::FromSize(i));
160 if (block->rpo_number() >= 0 && block->SuccessorCount() == 1) {
161 CHECK(block->rpo_number() + 1 == block->SuccessorAt(0)->rpo_number());
162 }
163 }
164 }
165 }
166
167
168 TEST(RPOSelfLoop) {
169 HandleAndZoneScope scope;
170 Schedule schedule(scope.main_zone());
171 schedule.AddSuccessorForTesting(schedule.start(), schedule.start());
172 BasicBlockVector* order =
173 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
174 CheckRPONumbers(order, 1, true);
175 BasicBlock* loop[] = {schedule.start()};
176 CheckLoop(order, loop, 1);
177 }
178
179
180 TEST(RPOEntryLoop) {
181 HandleAndZoneScope scope;
182 Schedule schedule(scope.main_zone());
183 BasicBlock* body = schedule.NewBasicBlock();
184 schedule.AddSuccessorForTesting(schedule.start(), body);
185 schedule.AddSuccessorForTesting(body, schedule.start());
186 BasicBlockVector* order =
187 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
188 CheckRPONumbers(order, 2, true);
189 BasicBlock* loop[] = {schedule.start(), body};
190 CheckLoop(order, loop, 2);
191 }
192
193
194 TEST(RPOEndLoop) {
195 HandleAndZoneScope scope;
196 Schedule schedule(scope.main_zone());
197 SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 2));
198 schedule.AddSuccessorForTesting(schedule.start(), loop1->header());
199 BasicBlockVector* order =
200 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
201 CheckRPONumbers(order, 3, true);
202 loop1->Check(order);
203 }
204
205
206 TEST(RPOEndLoopNested) {
207 HandleAndZoneScope scope;
208 Schedule schedule(scope.main_zone());
209 SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 2));
210 schedule.AddSuccessorForTesting(schedule.start(), loop1->header());
211 schedule.AddSuccessorForTesting(loop1->last(), schedule.start());
212 BasicBlockVector* order =
213 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
214 CheckRPONumbers(order, 3, true);
215 loop1->Check(order);
216 }
217
218
219 TEST(RPODiamond) {
220 HandleAndZoneScope scope;
221 Schedule schedule(scope.main_zone());
222
223 BasicBlock* A = schedule.start();
224 BasicBlock* B = schedule.NewBasicBlock();
225 BasicBlock* C = schedule.NewBasicBlock();
226 BasicBlock* D = schedule.end();
227
228 schedule.AddSuccessorForTesting(A, B);
229 schedule.AddSuccessorForTesting(A, C);
230 schedule.AddSuccessorForTesting(B, D);
231 schedule.AddSuccessorForTesting(C, D);
232
233 BasicBlockVector* order =
234 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
235 CheckRPONumbers(order, 4, false);
236
237 CHECK_EQ(0, A->rpo_number());
238 CHECK((B->rpo_number() == 1 && C->rpo_number() == 2) ||
239 (B->rpo_number() == 2 && C->rpo_number() == 1));
240 CHECK_EQ(3, D->rpo_number());
241 }
242
243
244 TEST(RPOLoop1) {
245 HandleAndZoneScope scope;
246 Schedule schedule(scope.main_zone());
247
248 BasicBlock* A = schedule.start();
249 BasicBlock* B = schedule.NewBasicBlock();
250 BasicBlock* C = schedule.NewBasicBlock();
251 BasicBlock* D = schedule.end();
252
253 schedule.AddSuccessorForTesting(A, B);
254 schedule.AddSuccessorForTesting(B, C);
255 schedule.AddSuccessorForTesting(C, B);
256 schedule.AddSuccessorForTesting(C, D);
257
258 BasicBlockVector* order =
259 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
260 CheckRPONumbers(order, 4, true);
261 BasicBlock* loop[] = {B, C};
262 CheckLoop(order, loop, 2);
263 }
264
265
266 TEST(RPOLoop2) {
267 HandleAndZoneScope scope;
268 Schedule schedule(scope.main_zone());
269
270 BasicBlock* A = schedule.start();
271 BasicBlock* B = schedule.NewBasicBlock();
272 BasicBlock* C = schedule.NewBasicBlock();
273 BasicBlock* D = schedule.end();
274
275 schedule.AddSuccessorForTesting(A, B);
276 schedule.AddSuccessorForTesting(B, C);
277 schedule.AddSuccessorForTesting(C, B);
278 schedule.AddSuccessorForTesting(B, D);
279
280 BasicBlockVector* order =
281 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
282 CheckRPONumbers(order, 4, true);
283 BasicBlock* loop[] = {B, C};
284 CheckLoop(order, loop, 2);
285 }
286
287
288 TEST(RPOLoopN) {
289 HandleAndZoneScope scope;
290
291 for (int i = 0; i < 11; i++) {
292 Schedule schedule(scope.main_zone());
293 BasicBlock* A = schedule.start();
294 BasicBlock* B = schedule.NewBasicBlock();
295 BasicBlock* C = schedule.NewBasicBlock();
296 BasicBlock* D = schedule.NewBasicBlock();
297 BasicBlock* E = schedule.NewBasicBlock();
298 BasicBlock* F = schedule.NewBasicBlock();
299 BasicBlock* G = schedule.end();
300
301 schedule.AddSuccessorForTesting(A, B);
302 schedule.AddSuccessorForTesting(B, C);
303 schedule.AddSuccessorForTesting(C, D);
304 schedule.AddSuccessorForTesting(D, E);
305 schedule.AddSuccessorForTesting(E, F);
306 schedule.AddSuccessorForTesting(F, B);
307 schedule.AddSuccessorForTesting(B, G);
308
309 // Throw in extra backedges from time to time.
310 if (i == 1) schedule.AddSuccessorForTesting(B, B);
311 if (i == 2) schedule.AddSuccessorForTesting(C, B);
312 if (i == 3) schedule.AddSuccessorForTesting(D, B);
313 if (i == 4) schedule.AddSuccessorForTesting(E, B);
314 if (i == 5) schedule.AddSuccessorForTesting(F, B);
315
316 // Throw in extra loop exits from time to time.
317 if (i == 6) schedule.AddSuccessorForTesting(B, G);
318 if (i == 7) schedule.AddSuccessorForTesting(C, G);
319 if (i == 8) schedule.AddSuccessorForTesting(D, G);
320 if (i == 9) schedule.AddSuccessorForTesting(E, G);
321 if (i == 10) schedule.AddSuccessorForTesting(F, G);
322
323 BasicBlockVector* order =
324 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
325 CheckRPONumbers(order, 7, true);
326 BasicBlock* loop[] = {B, C, D, E, F};
327 CheckLoop(order, loop, 5);
328 }
329 }
330
331
332 TEST(RPOLoopNest1) {
333 HandleAndZoneScope scope;
334 Schedule schedule(scope.main_zone());
335
336 BasicBlock* A = schedule.start();
337 BasicBlock* B = schedule.NewBasicBlock();
338 BasicBlock* C = schedule.NewBasicBlock();
339 BasicBlock* D = schedule.NewBasicBlock();
340 BasicBlock* E = schedule.NewBasicBlock();
341 BasicBlock* F = schedule.end();
342
343 schedule.AddSuccessorForTesting(A, B);
344 schedule.AddSuccessorForTesting(B, C);
345 schedule.AddSuccessorForTesting(C, D);
346 schedule.AddSuccessorForTesting(D, C);
347 schedule.AddSuccessorForTesting(D, E);
348 schedule.AddSuccessorForTesting(E, B);
349 schedule.AddSuccessorForTesting(E, F);
350
351 BasicBlockVector* order =
352 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
353 CheckRPONumbers(order, 6, true);
354 BasicBlock* loop1[] = {B, C, D, E};
355 CheckLoop(order, loop1, 4);
356
357 BasicBlock* loop2[] = {C, D};
358 CheckLoop(order, loop2, 2);
359 }
360
361
362 TEST(RPOLoopNest2) {
363 HandleAndZoneScope scope;
364 Schedule schedule(scope.main_zone());
365
366 BasicBlock* A = schedule.start();
367 BasicBlock* B = schedule.NewBasicBlock();
368 BasicBlock* C = schedule.NewBasicBlock();
369 BasicBlock* D = schedule.NewBasicBlock();
370 BasicBlock* E = schedule.NewBasicBlock();
371 BasicBlock* F = schedule.NewBasicBlock();
372 BasicBlock* G = schedule.NewBasicBlock();
373 BasicBlock* H = schedule.end();
374
375 schedule.AddSuccessorForTesting(A, B);
376 schedule.AddSuccessorForTesting(B, C);
377 schedule.AddSuccessorForTesting(C, D);
378 schedule.AddSuccessorForTesting(D, E);
379 schedule.AddSuccessorForTesting(E, F);
380 schedule.AddSuccessorForTesting(F, G);
381 schedule.AddSuccessorForTesting(G, H);
382
383 schedule.AddSuccessorForTesting(E, D);
384 schedule.AddSuccessorForTesting(F, C);
385 schedule.AddSuccessorForTesting(G, B);
386
387 BasicBlockVector* order =
388 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
389 CheckRPONumbers(order, 8, true);
390 BasicBlock* loop1[] = {B, C, D, E, F, G};
391 CheckLoop(order, loop1, 6);
392
393 BasicBlock* loop2[] = {C, D, E, F};
394 CheckLoop(order, loop2, 4);
395
396 BasicBlock* loop3[] = {D, E};
397 CheckLoop(order, loop3, 2);
398 }
399
400
401 TEST(RPOLoopFollow1) {
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* E = schedule.end();
410
411 schedule.AddSuccessorForTesting(A, loop1->header());
412 schedule.AddSuccessorForTesting(loop1->header(), loop2->header());
413 schedule.AddSuccessorForTesting(loop2->last(), E);
414
415 BasicBlockVector* order =
416 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
417
418 CHECK_EQ(static_cast<int>(schedule.BasicBlockCount()),
419 static_cast<int>(order->size()));
420
421 loop1->Check(order);
422 loop2->Check(order);
423 }
424
425
426 TEST(RPOLoopFollow2) {
427 HandleAndZoneScope scope;
428 Schedule schedule(scope.main_zone());
429
430 SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 1));
431 SmartPointer<TestLoop> loop2(CreateLoop(&schedule, 1));
432
433 BasicBlock* A = schedule.start();
434 BasicBlock* S = schedule.NewBasicBlock();
435 BasicBlock* E = schedule.end();
436
437 schedule.AddSuccessorForTesting(A, loop1->header());
438 schedule.AddSuccessorForTesting(loop1->header(), S);
439 schedule.AddSuccessorForTesting(S, loop2->header());
440 schedule.AddSuccessorForTesting(loop2->last(), E);
441
442 BasicBlockVector* order =
443 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
444
445 CHECK_EQ(static_cast<int>(schedule.BasicBlockCount()),
446 static_cast<int>(order->size()));
447 loop1->Check(order);
448 loop2->Check(order);
449 }
450
451
452 TEST(RPOLoopFollowN) {
453 HandleAndZoneScope scope;
454
455 for (int size = 1; size < 5; size++) {
456 for (int exit = 0; exit < size; exit++) {
457 Schedule schedule(scope.main_zone());
458 SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size));
459 SmartPointer<TestLoop> loop2(CreateLoop(&schedule, size));
460 BasicBlock* A = schedule.start();
461 BasicBlock* E = schedule.end();
462
463 schedule.AddSuccessorForTesting(A, loop1->header());
464 schedule.AddSuccessorForTesting(loop1->nodes[exit], loop2->header());
465 schedule.AddSuccessorForTesting(loop2->nodes[exit], E);
466 BasicBlockVector* order =
467 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
468
469 CHECK_EQ(static_cast<int>(schedule.BasicBlockCount()),
470 static_cast<int>(order->size()));
471 loop1->Check(order);
472 loop2->Check(order);
473 }
474 }
475 }
476
477
478 TEST(RPONestedLoopFollow1) {
479 HandleAndZoneScope scope;
480 Schedule schedule(scope.main_zone());
481
482 SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 1));
483 SmartPointer<TestLoop> loop2(CreateLoop(&schedule, 1));
484
485 BasicBlock* A = schedule.start();
486 BasicBlock* B = schedule.NewBasicBlock();
487 BasicBlock* C = schedule.NewBasicBlock();
488 BasicBlock* E = schedule.end();
489
490 schedule.AddSuccessorForTesting(A, B);
491 schedule.AddSuccessorForTesting(B, loop1->header());
492 schedule.AddSuccessorForTesting(loop1->header(), loop2->header());
493 schedule.AddSuccessorForTesting(loop2->last(), C);
494 schedule.AddSuccessorForTesting(C, E);
495 schedule.AddSuccessorForTesting(C, B);
496
497 BasicBlockVector* order =
498 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
499
500 CHECK_EQ(static_cast<int>(schedule.BasicBlockCount()),
501 static_cast<int>(order->size()));
502 loop1->Check(order);
503 loop2->Check(order);
504
505 BasicBlock* loop3[] = {B, loop1->nodes[0], loop2->nodes[0], C};
506 CheckLoop(order, loop3, 4);
507 }
508
509
510 TEST(RPOLoopBackedges1) {
511 HandleAndZoneScope scope;
512
513 int size = 8;
514 for (int i = 0; i < size; i++) {
515 for (int j = 0; j < size; j++) {
516 Schedule schedule(scope.main_zone());
517 BasicBlock* A = schedule.start();
518 BasicBlock* E = schedule.end();
519
520 SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size));
521 schedule.AddSuccessorForTesting(A, loop1->header());
522 schedule.AddSuccessorForTesting(loop1->last(), E);
523
524 schedule.AddSuccessorForTesting(loop1->nodes[i], loop1->header());
525 schedule.AddSuccessorForTesting(loop1->nodes[j], E);
526
527 BasicBlockVector* order =
528 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
529 CheckRPONumbers(order, schedule.BasicBlockCount(), true);
530 loop1->Check(order);
531 }
532 }
533 }
534
535
536 TEST(RPOLoopOutedges1) {
537 HandleAndZoneScope scope;
538
539 int size = 8;
540 for (int i = 0; i < size; i++) {
541 for (int j = 0; j < size; j++) {
542 Schedule schedule(scope.main_zone());
543 BasicBlock* A = schedule.start();
544 BasicBlock* D = schedule.NewBasicBlock();
545 BasicBlock* E = schedule.end();
546
547 SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size));
548 schedule.AddSuccessorForTesting(A, loop1->header());
549 schedule.AddSuccessorForTesting(loop1->last(), E);
550
551 schedule.AddSuccessorForTesting(loop1->nodes[i], loop1->header());
552 schedule.AddSuccessorForTesting(loop1->nodes[j], D);
553 schedule.AddSuccessorForTesting(D, E);
554
555 BasicBlockVector* order =
556 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
557 CheckRPONumbers(order, schedule.BasicBlockCount(), true);
558 loop1->Check(order);
559 }
560 }
561 }
562
563
564 TEST(RPOLoopOutedges2) {
565 HandleAndZoneScope scope;
566
567 int size = 8;
568 for (int i = 0; i < size; i++) {
569 Schedule schedule(scope.main_zone());
570 BasicBlock* A = schedule.start();
571 BasicBlock* E = schedule.end();
572
573 SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size));
574 schedule.AddSuccessorForTesting(A, loop1->header());
575 schedule.AddSuccessorForTesting(loop1->last(), E);
576
577 for (int j = 0; j < size; j++) {
578 BasicBlock* O = schedule.NewBasicBlock();
579 schedule.AddSuccessorForTesting(loop1->nodes[j], O);
580 schedule.AddSuccessorForTesting(O, E);
581 }
582
583 BasicBlockVector* order =
584 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
585 CheckRPONumbers(order, schedule.BasicBlockCount(), true);
586 loop1->Check(order);
587 }
588 }
589
590
591 TEST(RPOLoopOutloops1) {
592 HandleAndZoneScope scope;
593
594 int size = 8;
595 for (int i = 0; i < size; i++) {
596 Schedule schedule(scope.main_zone());
597 BasicBlock* A = schedule.start();
598 BasicBlock* E = schedule.end();
599 SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size));
600 schedule.AddSuccessorForTesting(A, loop1->header());
601 schedule.AddSuccessorForTesting(loop1->last(), E);
602
603 TestLoop** loopN = new TestLoop* [size];
604 for (int j = 0; j < size; j++) {
605 loopN[j] = CreateLoop(&schedule, 2);
606 schedule.AddSuccessorForTesting(loop1->nodes[j], loopN[j]->header());
607 schedule.AddSuccessorForTesting(loopN[j]->last(), E);
608 }
609
610 BasicBlockVector* order =
611 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
612 CheckRPONumbers(order, schedule.BasicBlockCount(), true);
613 loop1->Check(order);
614
615 for (int j = 0; j < size; j++) {
616 loopN[j]->Check(order);
617 delete loopN[j];
618 }
619 delete[] loopN;
620 }
621 }
622
623
624 TEST(RPOLoopMultibackedge) {
625 HandleAndZoneScope scope;
626 Schedule schedule(scope.main_zone());
627
628 BasicBlock* A = schedule.start();
629 BasicBlock* B = schedule.NewBasicBlock();
630 BasicBlock* C = schedule.NewBasicBlock();
631 BasicBlock* D = schedule.NewBasicBlock();
632 BasicBlock* E = schedule.NewBasicBlock();
633
634 schedule.AddSuccessorForTesting(A, B);
635 schedule.AddSuccessorForTesting(B, C);
636 schedule.AddSuccessorForTesting(B, D);
637 schedule.AddSuccessorForTesting(B, E);
638 schedule.AddSuccessorForTesting(C, B);
639 schedule.AddSuccessorForTesting(D, B);
640 schedule.AddSuccessorForTesting(E, B);
641
642 BasicBlockVector* order =
643 Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule);
644 CheckRPONumbers(order, 5, true);
645
646 BasicBlock* loop1[] = {B, C, D, E};
647 CheckLoop(order, loop1, 4);
648 }
649
650
651 TEST(BuildScheduleEmpty) {
652 HandleAndZoneScope scope;
653 Graph graph(scope.main_zone());
654 CommonOperatorBuilder builder(scope.main_zone());
655 graph.SetStart(graph.NewNode(builder.Start(0)));
656 graph.SetEnd(graph.NewNode(builder.End(), graph.start()));
657
658 USE(Scheduler::ComputeSchedule(scope.main_zone(), &graph));
659 }
660
661
662 TEST(BuildScheduleOneParameter) {
663 HandleAndZoneScope scope;
664 Graph graph(scope.main_zone());
665 CommonOperatorBuilder builder(scope.main_zone());
666 graph.SetStart(graph.NewNode(builder.Start(0)));
667
668 Node* p1 = graph.NewNode(builder.Parameter(0), graph.start());
669 Node* ret = graph.NewNode(builder.Return(), p1, graph.start(), graph.start());
670
671 graph.SetEnd(graph.NewNode(builder.End(), ret));
672
673 USE(Scheduler::ComputeSchedule(scope.main_zone(), &graph));
674 }
675
676
677 TEST(BuildScheduleIfSplit) {
678 HandleAndZoneScope scope;
679 Graph graph(scope.main_zone());
680 CommonOperatorBuilder builder(scope.main_zone());
681 JSOperatorBuilder js_builder(scope.main_zone());
682 graph.SetStart(graph.NewNode(builder.Start(3)));
683
684 Node* p1 = graph.NewNode(builder.Parameter(0), graph.start());
685 Node* p2 = graph.NewNode(builder.Parameter(1), graph.start());
686 Node* p3 = graph.NewNode(builder.Parameter(2), graph.start());
687 Node* p4 = graph.NewNode(builder.Parameter(3), graph.start());
688 Node* p5 = graph.NewNode(builder.Parameter(4), graph.start());
689 Node* cmp = graph.NewNode(js_builder.LessThanOrEqual(), p1, p2, p3,
690 graph.start(), graph.start());
691 Node* branch = graph.NewNode(builder.Branch(), cmp, graph.start());
692 Node* true_branch = graph.NewNode(builder.IfTrue(), branch);
693 Node* false_branch = graph.NewNode(builder.IfFalse(), branch);
694
695 Node* ret1 = graph.NewNode(builder.Return(), p4, graph.start(), true_branch);
696 Node* ret2 = graph.NewNode(builder.Return(), p5, graph.start(), false_branch);
697 Node* merge = graph.NewNode(builder.Merge(2), ret1, ret2);
698 graph.SetEnd(graph.NewNode(builder.End(), merge));
699
700 ComputeAndVerifySchedule(13, &graph);
701 }
702
703
704 TEST(BuildScheduleIfSplitWithEffects) {
705 HandleAndZoneScope scope;
706 Isolate* isolate = scope.main_isolate();
707 Graph graph(scope.main_zone());
708 CommonOperatorBuilder common_builder(scope.main_zone());
709 JSOperatorBuilder js_builder(scope.main_zone());
710 const Operator* op;
711
712 Handle<HeapObject> object =
713 Handle<HeapObject>(isolate->heap()->undefined_value(), isolate);
714 Unique<HeapObject> unique_constant =
715 Unique<HeapObject>::CreateUninitialized(object);
716
717 // Manually transcripted code for:
718 // function turbo_fan_test(a, b, c, y) {
719 // if (a < b) {
720 // return a + b - c * c - a + y;
721 // } else {
722 // return c * c - a;
723 // }
724 // }
725 op = common_builder.Start(0);
726 Node* n0 = graph.NewNode(op);
727 USE(n0);
728 Node* nil = graph.NewNode(common_builder.Dead());
729 op = common_builder.End();
730 Node* n23 = graph.NewNode(op, nil);
731 USE(n23);
732 op = common_builder.Merge(2);
733 Node* n22 = graph.NewNode(op, nil, nil);
734 USE(n22);
735 op = common_builder.Return();
736 Node* n16 = graph.NewNode(op, nil, nil, nil);
737 USE(n16);
738 op = js_builder.Add();
739 Node* n15 = graph.NewNode(op, nil, nil, nil, nil, nil);
740 USE(n15);
741 op = js_builder.Subtract();
742 Node* n14 = graph.NewNode(op, nil, nil, nil, nil, nil);
743 USE(n14);
744 op = js_builder.Subtract();
745 Node* n13 = graph.NewNode(op, nil, nil, nil, nil, nil);
746 USE(n13);
747 op = js_builder.Add();
748 Node* n11 = graph.NewNode(op, nil, nil, nil, nil, nil);
749 USE(n11);
750 op = common_builder.Parameter(0);
751 Node* n2 = graph.NewNode(op, n0);
752 USE(n2);
753 n11->ReplaceInput(0, n2);
754 op = common_builder.Parameter(0);
755 Node* n3 = graph.NewNode(op, n0);
756 USE(n3);
757 n11->ReplaceInput(1, n3);
758 op = common_builder.HeapConstant(unique_constant);
759 Node* n7 = graph.NewNode(op);
760 USE(n7);
761 n11->ReplaceInput(2, n7);
762 op = js_builder.LessThan();
763 Node* n8 = graph.NewNode(op, nil, nil, nil, nil, nil);
764 USE(n8);
765 n8->ReplaceInput(0, n2);
766 n8->ReplaceInput(1, n3);
767 n8->ReplaceInput(2, n7);
768 n8->ReplaceInput(3, n0);
769 n8->ReplaceInput(4, n0);
770 n11->ReplaceInput(3, n8);
771 op = common_builder.IfTrue();
772 Node* n10 = graph.NewNode(op, nil);
773 USE(n10);
774 op = common_builder.Branch();
775 Node* n9 = graph.NewNode(op, nil, nil);
776 USE(n9);
777 n9->ReplaceInput(0, n8);
778 n9->ReplaceInput(1, n0);
779 n10->ReplaceInput(0, n9);
780 n11->ReplaceInput(4, n10);
781 n13->ReplaceInput(0, n11);
782 op = js_builder.Multiply();
783 Node* n12 = graph.NewNode(op, nil, nil, nil, nil, nil);
784 USE(n12);
785 op = common_builder.Parameter(0);
786 Node* n4 = graph.NewNode(op, n0);
787 USE(n4);
788 n12->ReplaceInput(0, n4);
789 n12->ReplaceInput(1, n4);
790 n12->ReplaceInput(2, n7);
791 n12->ReplaceInput(3, n11);
792 n12->ReplaceInput(4, n10);
793 n13->ReplaceInput(1, n12);
794 n13->ReplaceInput(2, n7);
795 n13->ReplaceInput(3, n12);
796 n13->ReplaceInput(4, n10);
797 n14->ReplaceInput(0, n13);
798 n14->ReplaceInput(1, n2);
799 n14->ReplaceInput(2, n7);
800 n14->ReplaceInput(3, n13);
801 n14->ReplaceInput(4, n10);
802 n15->ReplaceInput(0, n14);
803 op = common_builder.Parameter(0);
804 Node* n5 = graph.NewNode(op, n0);
805 USE(n5);
806 n15->ReplaceInput(1, n5);
807 n15->ReplaceInput(2, n7);
808 n15->ReplaceInput(3, n14);
809 n15->ReplaceInput(4, n10);
810 n16->ReplaceInput(0, n15);
811 n16->ReplaceInput(1, n15);
812 n16->ReplaceInput(2, n10);
813 n22->ReplaceInput(0, n16);
814 op = common_builder.Return();
815 Node* n21 = graph.NewNode(op, nil, nil, nil);
816 USE(n21);
817 op = js_builder.Subtract();
818 Node* n20 = graph.NewNode(op, nil, nil, nil, nil, nil);
819 USE(n20);
820 op = js_builder.Multiply();
821 Node* n19 = graph.NewNode(op, nil, nil, nil, nil, nil);
822 USE(n19);
823 n19->ReplaceInput(0, n4);
824 n19->ReplaceInput(1, n4);
825 n19->ReplaceInput(2, n7);
826 n19->ReplaceInput(3, n8);
827 op = common_builder.IfFalse();
828 Node* n18 = graph.NewNode(op, nil);
829 USE(n18);
830 n18->ReplaceInput(0, n9);
831 n19->ReplaceInput(4, n18);
832 n20->ReplaceInput(0, n19);
833 n20->ReplaceInput(1, n2);
834 n20->ReplaceInput(2, n7);
835 n20->ReplaceInput(3, n19);
836 n20->ReplaceInput(4, n18);
837 n21->ReplaceInput(0, n20);
838 n21->ReplaceInput(1, n20);
839 n21->ReplaceInput(2, n18);
840 n22->ReplaceInput(1, n21);
841 n23->ReplaceInput(0, n22);
842
843 graph.SetStart(n0);
844 graph.SetEnd(n23);
845
846 ComputeAndVerifySchedule(20, &graph);
847 }
848
849
850 TEST(BuildScheduleSimpleLoop) {
851 HandleAndZoneScope scope;
852 Isolate* isolate = scope.main_isolate();
853 Graph graph(scope.main_zone());
854 CommonOperatorBuilder common_builder(scope.main_zone());
855 JSOperatorBuilder js_builder(scope.main_zone());
856 const Operator* op;
857
858 Handle<HeapObject> object =
859 Handle<HeapObject>(isolate->heap()->undefined_value(), isolate);
860 Unique<HeapObject> unique_constant =
861 Unique<HeapObject>::CreateUninitialized(object);
862
863 // Manually transcripted code for:
864 // function turbo_fan_test(a, b) {
865 // while (a < b) {
866 // a++;
867 // }
868 // return a;
869 // }
870 op = common_builder.Start(0);
871 Node* n0 = graph.NewNode(op);
872 USE(n0);
873 Node* nil = graph.NewNode(common_builder.Dead());
874 op = common_builder.End();
875 Node* n20 = graph.NewNode(op, nil);
876 USE(n20);
877 op = common_builder.Return();
878 Node* n19 = graph.NewNode(op, nil, nil, nil);
879 USE(n19);
880 op = common_builder.Phi(kMachAnyTagged, 2);
881 Node* n8 = graph.NewNode(op, nil, nil, nil);
882 USE(n8);
883 op = common_builder.Parameter(0);
884 Node* n2 = graph.NewNode(op, n0);
885 USE(n2);
886 n8->ReplaceInput(0, n2);
887 op = js_builder.Add();
888 Node* n18 = graph.NewNode(op, nil, nil, nil, nil, nil);
889 USE(n18);
890 op = js_builder.ToNumber();
891 Node* n16 = graph.NewNode(op, nil, nil, nil, nil);
892 USE(n16);
893 n16->ReplaceInput(0, n8);
894 op = common_builder.HeapConstant(unique_constant);
895 Node* n5 = graph.NewNode(op);
896 USE(n5);
897 n16->ReplaceInput(1, n5);
898 op = js_builder.LessThan();
899 Node* n12 = graph.NewNode(op, nil, nil, nil, nil, nil);
900 USE(n12);
901 n12->ReplaceInput(0, n8);
902 op = common_builder.Phi(kMachAnyTagged, 2);
903 Node* n9 = graph.NewNode(op, nil, nil, nil);
904 USE(n9);
905 op = common_builder.Parameter(0);
906 Node* n3 = graph.NewNode(op, n0);
907 USE(n3);
908 n9->ReplaceInput(0, n3);
909 n9->ReplaceInput(1, n9);
910 op = common_builder.Loop(2);
911 Node* n6 = graph.NewNode(op, nil, nil);
912 USE(n6);
913 n6->ReplaceInput(0, n0);
914 op = common_builder.IfTrue();
915 Node* n14 = graph.NewNode(op, nil);
916 USE(n14);
917 op = common_builder.Branch();
918 Node* n13 = graph.NewNode(op, nil, nil);
919 USE(n13);
920 n13->ReplaceInput(0, n12);
921 n13->ReplaceInput(1, n6);
922 n14->ReplaceInput(0, n13);
923 n6->ReplaceInput(1, n14);
924 n9->ReplaceInput(2, n6);
925 n12->ReplaceInput(1, n9);
926 n12->ReplaceInput(2, n5);
927 op = common_builder.Phi(kMachAnyTagged, 2);
928 Node* n10 = graph.NewNode(op, nil, nil, nil);
929 USE(n10);
930 n10->ReplaceInput(0, n0);
931 n10->ReplaceInput(1, n18);
932 n10->ReplaceInput(2, n6);
933 n12->ReplaceInput(3, n10);
934 n12->ReplaceInput(4, n6);
935 n16->ReplaceInput(2, n12);
936 n16->ReplaceInput(3, n14);
937 n18->ReplaceInput(0, n16);
938 op = common_builder.NumberConstant(0);
939 Node* n17 = graph.NewNode(op);
940 USE(n17);
941 n18->ReplaceInput(1, n17);
942 n18->ReplaceInput(2, n5);
943 n18->ReplaceInput(3, n16);
944 n18->ReplaceInput(4, n14);
945 n8->ReplaceInput(1, n18);
946 n8->ReplaceInput(2, n6);
947 n19->ReplaceInput(0, n8);
948 n19->ReplaceInput(1, n12);
949 op = common_builder.IfFalse();
950 Node* n15 = graph.NewNode(op, nil);
951 USE(n15);
952 n15->ReplaceInput(0, n13);
953 n19->ReplaceInput(2, n15);
954 n20->ReplaceInput(0, n19);
955
956 graph.SetStart(n0);
957 graph.SetEnd(n20);
958
959 ComputeAndVerifySchedule(19, &graph);
960 }
961
962
963 TEST(BuildScheduleComplexLoops) {
964 HandleAndZoneScope scope;
965 Isolate* isolate = scope.main_isolate();
966 Graph graph(scope.main_zone());
967 CommonOperatorBuilder common_builder(scope.main_zone());
968 JSOperatorBuilder js_builder(scope.main_zone());
969 const Operator* op;
970
971 Handle<HeapObject> object =
972 Handle<HeapObject>(isolate->heap()->undefined_value(), isolate);
973 Unique<HeapObject> unique_constant =
974 Unique<HeapObject>::CreateUninitialized(object);
975
976 // Manually transcripted code for:
977 // function turbo_fan_test(a, b, c) {
978 // while (a < b) {
979 // a++;
980 // while (c < b) {
981 // c++;
982 // }
983 // }
984 // while (a < b) {
985 // a += 2;
986 // }
987 // return a;
988 // }
989 op = common_builder.Start(0);
990 Node* n0 = graph.NewNode(op);
991 USE(n0);
992 Node* nil = graph.NewNode(common_builder.Dead());
993 op = common_builder.End();
994 Node* n46 = graph.NewNode(op, nil);
995 USE(n46);
996 op = common_builder.Return();
997 Node* n45 = graph.NewNode(op, nil, nil, nil);
998 USE(n45);
999 op = common_builder.Phi(kMachAnyTagged, 2);
1000 Node* n35 = graph.NewNode(op, nil, nil, nil);
1001 USE(n35);
1002 op = common_builder.Phi(kMachAnyTagged, 2);
1003 Node* n9 = graph.NewNode(op, nil, nil, nil);
1004 USE(n9);
1005 op = common_builder.Parameter(0);
1006 Node* n2 = graph.NewNode(op, n0);
1007 USE(n2);
1008 n9->ReplaceInput(0, n2);
1009 op = common_builder.Phi(kMachAnyTagged, 2);
1010 Node* n23 = graph.NewNode(op, nil, nil, nil);
1011 USE(n23);
1012 op = js_builder.Add();
1013 Node* n20 = graph.NewNode(op, nil, nil, nil, nil, nil);
1014 USE(n20);
1015 op = js_builder.ToNumber();
1016 Node* n18 = graph.NewNode(op, nil, nil, nil, nil);
1017 USE(n18);
1018 n18->ReplaceInput(0, n9);
1019 op = common_builder.HeapConstant(unique_constant);
1020 Node* n6 = graph.NewNode(op);
1021 USE(n6);
1022 n18->ReplaceInput(1, n6);
1023 op = js_builder.LessThan();
1024 Node* n14 = graph.NewNode(op, nil, nil, nil, nil, nil);
1025 USE(n14);
1026 n14->ReplaceInput(0, n9);
1027 op = common_builder.Phi(kMachAnyTagged, 2);
1028 Node* n10 = graph.NewNode(op, nil, nil, nil);
1029 USE(n10);
1030 op = common_builder.Parameter(0);
1031 Node* n3 = graph.NewNode(op, n0);
1032 USE(n3);
1033 n10->ReplaceInput(0, n3);
1034 op = common_builder.Phi(kMachAnyTagged, 2);
1035 Node* n24 = graph.NewNode(op, nil, nil, nil);
1036 USE(n24);
1037 n24->ReplaceInput(0, n10);
1038 n24->ReplaceInput(1, n24);
1039 op = common_builder.Loop(2);
1040 Node* n21 = graph.NewNode(op, nil, nil);
1041 USE(n21);
1042 op = common_builder.IfTrue();
1043 Node* n16 = graph.NewNode(op, nil);
1044 USE(n16);
1045 op = common_builder.Branch();
1046 Node* n15 = graph.NewNode(op, nil, nil);
1047 USE(n15);
1048 n15->ReplaceInput(0, n14);
1049 op = common_builder.Loop(2);
1050 Node* n7 = graph.NewNode(op, nil, nil);
1051 USE(n7);
1052 n7->ReplaceInput(0, n0);
1053 op = common_builder.IfFalse();
1054 Node* n30 = graph.NewNode(op, nil);
1055 USE(n30);
1056 op = common_builder.Branch();
1057 Node* n28 = graph.NewNode(op, nil, nil);
1058 USE(n28);
1059 op = js_builder.LessThan();
1060 Node* n27 = graph.NewNode(op, nil, nil, nil, nil, nil);
1061 USE(n27);
1062 op = common_builder.Phi(kMachAnyTagged, 2);
1063 Node* n25 = graph.NewNode(op, nil, nil, nil);
1064 USE(n25);
1065 op = common_builder.Phi(kMachAnyTagged, 2);
1066 Node* n11 = graph.NewNode(op, nil, nil, nil);
1067 USE(n11);
1068 op = common_builder.Parameter(0);
1069 Node* n4 = graph.NewNode(op, n0);
1070 USE(n4);
1071 n11->ReplaceInput(0, n4);
1072 n11->ReplaceInput(1, n25);
1073 n11->ReplaceInput(2, n7);
1074 n25->ReplaceInput(0, n11);
1075 op = js_builder.Add();
1076 Node* n32 = graph.NewNode(op, nil, nil, nil, nil, nil);
1077 USE(n32);
1078 op = js_builder.ToNumber();
1079 Node* n31 = graph.NewNode(op, nil, nil, nil, nil);
1080 USE(n31);
1081 n31->ReplaceInput(0, n25);
1082 n31->ReplaceInput(1, n6);
1083 n31->ReplaceInput(2, n27);
1084 op = common_builder.IfTrue();
1085 Node* n29 = graph.NewNode(op, nil);
1086 USE(n29);
1087 n29->ReplaceInput(0, n28);
1088 n31->ReplaceInput(3, n29);
1089 n32->ReplaceInput(0, n31);
1090 op = common_builder.NumberConstant(0);
1091 Node* n19 = graph.NewNode(op);
1092 USE(n19);
1093 n32->ReplaceInput(1, n19);
1094 n32->ReplaceInput(2, n6);
1095 n32->ReplaceInput(3, n31);
1096 n32->ReplaceInput(4, n29);
1097 n25->ReplaceInput(1, n32);
1098 n25->ReplaceInput(2, n21);
1099 n27->ReplaceInput(0, n25);
1100 n27->ReplaceInput(1, n24);
1101 n27->ReplaceInput(2, n6);
1102 op = common_builder.Phi(kMachAnyTagged, 2);
1103 Node* n26 = graph.NewNode(op, nil, nil, nil);
1104 USE(n26);
1105 n26->ReplaceInput(0, n20);
1106 n26->ReplaceInput(1, n32);
1107 n26->ReplaceInput(2, n21);
1108 n27->ReplaceInput(3, n26);
1109 n27->ReplaceInput(4, n21);
1110 n28->ReplaceInput(0, n27);
1111 n28->ReplaceInput(1, n21);
1112 n30->ReplaceInput(0, n28);
1113 n7->ReplaceInput(1, n30);
1114 n15->ReplaceInput(1, n7);
1115 n16->ReplaceInput(0, n15);
1116 n21->ReplaceInput(0, n16);
1117 n21->ReplaceInput(1, n29);
1118 n24->ReplaceInput(2, n21);
1119 n10->ReplaceInput(1, n24);
1120 n10->ReplaceInput(2, n7);
1121 n14->ReplaceInput(1, n10);
1122 n14->ReplaceInput(2, n6);
1123 op = common_builder.Phi(kMachAnyTagged, 2);
1124 Node* n12 = graph.NewNode(op, nil, nil, nil);
1125 USE(n12);
1126 n12->ReplaceInput(0, n0);
1127 n12->ReplaceInput(1, n27);
1128 n12->ReplaceInput(2, n7);
1129 n14->ReplaceInput(3, n12);
1130 n14->ReplaceInput(4, n7);
1131 n18->ReplaceInput(2, n14);
1132 n18->ReplaceInput(3, n16);
1133 n20->ReplaceInput(0, n18);
1134 n20->ReplaceInput(1, n19);
1135 n20->ReplaceInput(2, n6);
1136 n20->ReplaceInput(3, n18);
1137 n20->ReplaceInput(4, n16);
1138 n23->ReplaceInput(0, n20);
1139 n23->ReplaceInput(1, n23);
1140 n23->ReplaceInput(2, n21);
1141 n9->ReplaceInput(1, n23);
1142 n9->ReplaceInput(2, n7);
1143 n35->ReplaceInput(0, n9);
1144 op = js_builder.Add();
1145 Node* n44 = graph.NewNode(op, nil, nil, nil, nil, nil);
1146 USE(n44);
1147 n44->ReplaceInput(0, n35);
1148 op = common_builder.NumberConstant(0);
1149 Node* n43 = graph.NewNode(op);
1150 USE(n43);
1151 n44->ReplaceInput(1, n43);
1152 n44->ReplaceInput(2, n6);
1153 op = js_builder.LessThan();
1154 Node* n39 = graph.NewNode(op, nil, nil, nil, nil, nil);
1155 USE(n39);
1156 n39->ReplaceInput(0, n35);
1157 op = common_builder.Phi(kMachAnyTagged, 2);
1158 Node* n36 = graph.NewNode(op, nil, nil, nil);
1159 USE(n36);
1160 n36->ReplaceInput(0, n10);
1161 n36->ReplaceInput(1, n36);
1162 op = common_builder.Loop(2);
1163 Node* n33 = graph.NewNode(op, nil, nil);
1164 USE(n33);
1165 op = common_builder.IfFalse();
1166 Node* n17 = graph.NewNode(op, nil);
1167 USE(n17);
1168 n17->ReplaceInput(0, n15);
1169 n33->ReplaceInput(0, n17);
1170 op = common_builder.IfTrue();
1171 Node* n41 = graph.NewNode(op, nil);
1172 USE(n41);
1173 op = common_builder.Branch();
1174 Node* n40 = graph.NewNode(op, nil, nil);
1175 USE(n40);
1176 n40->ReplaceInput(0, n39);
1177 n40->ReplaceInput(1, n33);
1178 n41->ReplaceInput(0, n40);
1179 n33->ReplaceInput(1, n41);
1180 n36->ReplaceInput(2, n33);
1181 n39->ReplaceInput(1, n36);
1182 n39->ReplaceInput(2, n6);
1183 op = common_builder.Phi(kMachAnyTagged, 2);
1184 Node* n38 = graph.NewNode(op, nil, nil, nil);
1185 USE(n38);
1186 n38->ReplaceInput(0, n14);
1187 n38->ReplaceInput(1, n44);
1188 n38->ReplaceInput(2, n33);
1189 n39->ReplaceInput(3, n38);
1190 n39->ReplaceInput(4, n33);
1191 n44->ReplaceInput(3, n39);
1192 n44->ReplaceInput(4, n41);
1193 n35->ReplaceInput(1, n44);
1194 n35->ReplaceInput(2, n33);
1195 n45->ReplaceInput(0, n35);
1196 n45->ReplaceInput(1, n39);
1197 op = common_builder.IfFalse();
1198 Node* n42 = graph.NewNode(op, nil);
1199 USE(n42);
1200 n42->ReplaceInput(0, n40);
1201 n45->ReplaceInput(2, n42);
1202 n46->ReplaceInput(0, n45);
1203
1204 graph.SetStart(n0);
1205 graph.SetEnd(n46);
1206
1207 ComputeAndVerifySchedule(46, &graph);
1208 }
1209
1210
1211 TEST(BuildScheduleBreakAndContinue) {
1212 HandleAndZoneScope scope;
1213 Isolate* isolate = scope.main_isolate();
1214 Graph graph(scope.main_zone());
1215 CommonOperatorBuilder common_builder(scope.main_zone());
1216 JSOperatorBuilder js_builder(scope.main_zone());
1217 const Operator* op;
1218
1219 Handle<HeapObject> object =
1220 Handle<HeapObject>(isolate->heap()->undefined_value(), isolate);
1221 Unique<HeapObject> unique_constant =
1222 Unique<HeapObject>::CreateUninitialized(object);
1223
1224 // Manually transcripted code for:
1225 // function turbo_fan_test(a, b, c) {
1226 // var d = 0;
1227 // while (a < b) {
1228 // a++;
1229 // while (c < b) {
1230 // c++;
1231 // if (d == 0) break;
1232 // a++;
1233 // }
1234 // if (a == 1) continue;
1235 // d++;
1236 // }
1237 // return a + d;
1238 // }
1239 op = common_builder.Start(0);
1240 Node* n0 = graph.NewNode(op);
1241 USE(n0);
1242 Node* nil = graph.NewNode(common_builder.Dead());
1243 op = common_builder.End();
1244 Node* n58 = graph.NewNode(op, nil);
1245 USE(n58);
1246 op = common_builder.Return();
1247 Node* n57 = graph.NewNode(op, nil, nil, nil);
1248 USE(n57);
1249 op = js_builder.Add();
1250 Node* n56 = graph.NewNode(op, nil, nil, nil, nil, nil);
1251 USE(n56);
1252 op = common_builder.Phi(kMachAnyTagged, 2);
1253 Node* n10 = graph.NewNode(op, nil, nil, nil);
1254 USE(n10);
1255 op = common_builder.Parameter(0);
1256 Node* n2 = graph.NewNode(op, n0);
1257 USE(n2);
1258 n10->ReplaceInput(0, n2);
1259 op = common_builder.Phi(kMachAnyTagged, 2);
1260 Node* n25 = graph.NewNode(op, nil, nil, nil);
1261 USE(n25);
1262 op = js_builder.Add();
1263 Node* n22 = graph.NewNode(op, nil, nil, nil, nil, nil);
1264 USE(n22);
1265 op = js_builder.ToNumber();
1266 Node* n20 = graph.NewNode(op, nil, nil, nil, nil);
1267 USE(n20);
1268 n20->ReplaceInput(0, n10);
1269 op = common_builder.HeapConstant(unique_constant);
1270 Node* n6 = graph.NewNode(op);
1271 USE(n6);
1272 n20->ReplaceInput(1, n6);
1273 op = js_builder.LessThan();
1274 Node* n16 = graph.NewNode(op, nil, nil, nil, nil, nil);
1275 USE(n16);
1276 n16->ReplaceInput(0, n10);
1277 op = common_builder.Phi(kMachAnyTagged, 2);
1278 Node* n11 = graph.NewNode(op, nil, nil, nil);
1279 USE(n11);
1280 op = common_builder.Parameter(0);
1281 Node* n3 = graph.NewNode(op, n0);
1282 USE(n3);
1283 n11->ReplaceInput(0, n3);
1284 op = common_builder.Phi(kMachAnyTagged, 2);
1285 Node* n26 = graph.NewNode(op, nil, nil, nil);
1286 USE(n26);
1287 n26->ReplaceInput(0, n11);
1288 n26->ReplaceInput(1, n26);
1289 op = common_builder.Loop(2);
1290 Node* n23 = graph.NewNode(op, nil, nil);
1291 USE(n23);
1292 op = common_builder.IfTrue();
1293 Node* n18 = graph.NewNode(op, nil);
1294 USE(n18);
1295 op = common_builder.Branch();
1296 Node* n17 = graph.NewNode(op, nil, nil);
1297 USE(n17);
1298 n17->ReplaceInput(0, n16);
1299 op = common_builder.Loop(2);
1300 Node* n8 = graph.NewNode(op, nil, nil);
1301 USE(n8);
1302 n8->ReplaceInput(0, n0);
1303 op = common_builder.Merge(2);
1304 Node* n53 = graph.NewNode(op, nil, nil);
1305 USE(n53);
1306 op = common_builder.IfTrue();
1307 Node* n49 = graph.NewNode(op, nil);
1308 USE(n49);
1309 op = common_builder.Branch();
1310 Node* n48 = graph.NewNode(op, nil, nil);
1311 USE(n48);
1312 op = js_builder.Equal();
1313 Node* n47 = graph.NewNode(op, nil, nil, nil, nil, nil);
1314 USE(n47);
1315 n47->ReplaceInput(0, n25);
1316 op = common_builder.NumberConstant(0);
1317 Node* n46 = graph.NewNode(op);
1318 USE(n46);
1319 n47->ReplaceInput(1, n46);
1320 n47->ReplaceInput(2, n6);
1321 op = common_builder.Phi(kMachAnyTagged, 2);
1322 Node* n42 = graph.NewNode(op, nil, nil, nil);
1323 USE(n42);
1324 op = js_builder.LessThan();
1325 Node* n30 = graph.NewNode(op, nil, nil, nil, nil, nil);
1326 USE(n30);
1327 op = common_builder.Phi(kMachAnyTagged, 2);
1328 Node* n27 = graph.NewNode(op, nil, nil, nil);
1329 USE(n27);
1330 op = common_builder.Phi(kMachAnyTagged, 2);
1331 Node* n12 = graph.NewNode(op, nil, nil, nil);
1332 USE(n12);
1333 op = common_builder.Parameter(0);
1334 Node* n4 = graph.NewNode(op, n0);
1335 USE(n4);
1336 n12->ReplaceInput(0, n4);
1337 op = common_builder.Phi(kMachAnyTagged, 2);
1338 Node* n41 = graph.NewNode(op, nil, nil, nil);
1339 USE(n41);
1340 n41->ReplaceInput(0, n27);
1341 op = js_builder.Add();
1342 Node* n35 = graph.NewNode(op, nil, nil, nil, nil, nil);
1343 USE(n35);
1344 op = js_builder.ToNumber();
1345 Node* n34 = graph.NewNode(op, nil, nil, nil, nil);
1346 USE(n34);
1347 n34->ReplaceInput(0, n27);
1348 n34->ReplaceInput(1, n6);
1349 n34->ReplaceInput(2, n30);
1350 op = common_builder.IfTrue();
1351 Node* n32 = graph.NewNode(op, nil);
1352 USE(n32);
1353 op = common_builder.Branch();
1354 Node* n31 = graph.NewNode(op, nil, nil);
1355 USE(n31);
1356 n31->ReplaceInput(0, n30);
1357 n31->ReplaceInput(1, n23);
1358 n32->ReplaceInput(0, n31);
1359 n34->ReplaceInput(3, n32);
1360 n35->ReplaceInput(0, n34);
1361 op = common_builder.NumberConstant(0);
1362 Node* n21 = graph.NewNode(op);
1363 USE(n21);
1364 n35->ReplaceInput(1, n21);
1365 n35->ReplaceInput(2, n6);
1366 n35->ReplaceInput(3, n34);
1367 n35->ReplaceInput(4, n32);
1368 n41->ReplaceInput(1, n35);
1369 op = common_builder.Merge(2);
1370 Node* n40 = graph.NewNode(op, nil, nil);
1371 USE(n40);
1372 op = common_builder.IfFalse();
1373 Node* n33 = graph.NewNode(op, nil);
1374 USE(n33);
1375 n33->ReplaceInput(0, n31);
1376 n40->ReplaceInput(0, n33);
1377 op = common_builder.IfTrue();
1378 Node* n39 = graph.NewNode(op, nil);
1379 USE(n39);
1380 op = common_builder.Branch();
1381 Node* n38 = graph.NewNode(op, nil, nil);
1382 USE(n38);
1383 op = js_builder.Equal();
1384 Node* n37 = graph.NewNode(op, nil, nil, nil, nil, nil);
1385 USE(n37);
1386 op = common_builder.Phi(kMachAnyTagged, 2);
1387 Node* n28 = graph.NewNode(op, nil, nil, nil);
1388 USE(n28);
1389 op = common_builder.Phi(kMachAnyTagged, 2);
1390 Node* n13 = graph.NewNode(op, nil, nil, nil);
1391 USE(n13);
1392 op = common_builder.NumberConstant(0);
1393 Node* n7 = graph.NewNode(op);
1394 USE(n7);
1395 n13->ReplaceInput(0, n7);
1396 op = common_builder.Phi(kMachAnyTagged, 2);
1397 Node* n54 = graph.NewNode(op, nil, nil, nil);
1398 USE(n54);
1399 n54->ReplaceInput(0, n28);
1400 op = js_builder.Add();
1401 Node* n52 = graph.NewNode(op, nil, nil, nil, nil, nil);
1402 USE(n52);
1403 op = js_builder.ToNumber();
1404 Node* n51 = graph.NewNode(op, nil, nil, nil, nil);
1405 USE(n51);
1406 n51->ReplaceInput(0, n28);
1407 n51->ReplaceInput(1, n6);
1408 n51->ReplaceInput(2, n47);
1409 op = common_builder.IfFalse();
1410 Node* n50 = graph.NewNode(op, nil);
1411 USE(n50);
1412 n50->ReplaceInput(0, n48);
1413 n51->ReplaceInput(3, n50);
1414 n52->ReplaceInput(0, n51);
1415 n52->ReplaceInput(1, n21);
1416 n52->ReplaceInput(2, n6);
1417 n52->ReplaceInput(3, n51);
1418 n52->ReplaceInput(4, n50);
1419 n54->ReplaceInput(1, n52);
1420 n54->ReplaceInput(2, n53);
1421 n13->ReplaceInput(1, n54);
1422 n13->ReplaceInput(2, n8);
1423 n28->ReplaceInput(0, n13);
1424 n28->ReplaceInput(1, n28);
1425 n28->ReplaceInput(2, n23);
1426 n37->ReplaceInput(0, n28);
1427 op = common_builder.NumberConstant(0);
1428 Node* n36 = graph.NewNode(op);
1429 USE(n36);
1430 n37->ReplaceInput(1, n36);
1431 n37->ReplaceInput(2, n6);
1432 n37->ReplaceInput(3, n35);
1433 n37->ReplaceInput(4, n32);
1434 n38->ReplaceInput(0, n37);
1435 n38->ReplaceInput(1, n32);
1436 n39->ReplaceInput(0, n38);
1437 n40->ReplaceInput(1, n39);
1438 n41->ReplaceInput(2, n40);
1439 n12->ReplaceInput(1, n41);
1440 n12->ReplaceInput(2, n8);
1441 n27->ReplaceInput(0, n12);
1442 n27->ReplaceInput(1, n35);
1443 n27->ReplaceInput(2, n23);
1444 n30->ReplaceInput(0, n27);
1445 n30->ReplaceInput(1, n26);
1446 n30->ReplaceInput(2, n6);
1447 op = common_builder.Phi(kMachAnyTagged, 2);
1448 Node* n29 = graph.NewNode(op, nil, nil, nil);
1449 USE(n29);
1450 n29->ReplaceInput(0, n22);
1451 op = js_builder.Add();
1452 Node* n45 = graph.NewNode(op, nil, nil, nil, nil, nil);
1453 USE(n45);
1454 op = js_builder.ToNumber();
1455 Node* n44 = graph.NewNode(op, nil, nil, nil, nil);
1456 USE(n44);
1457 n44->ReplaceInput(0, n25);
1458 n44->ReplaceInput(1, n6);
1459 n44->ReplaceInput(2, n37);
1460 op = common_builder.IfFalse();
1461 Node* n43 = graph.NewNode(op, nil);
1462 USE(n43);
1463 n43->ReplaceInput(0, n38);
1464 n44->ReplaceInput(3, n43);
1465 n45->ReplaceInput(0, n44);
1466 n45->ReplaceInput(1, n21);
1467 n45->ReplaceInput(2, n6);
1468 n45->ReplaceInput(3, n44);
1469 n45->ReplaceInput(4, n43);
1470 n29->ReplaceInput(1, n45);
1471 n29->ReplaceInput(2, n23);
1472 n30->ReplaceInput(3, n29);
1473 n30->ReplaceInput(4, n23);
1474 n42->ReplaceInput(0, n30);
1475 n42->ReplaceInput(1, n37);
1476 n42->ReplaceInput(2, n40);
1477 n47->ReplaceInput(3, n42);
1478 n47->ReplaceInput(4, n40);
1479 n48->ReplaceInput(0, n47);
1480 n48->ReplaceInput(1, n40);
1481 n49->ReplaceInput(0, n48);
1482 n53->ReplaceInput(0, n49);
1483 n53->ReplaceInput(1, n50);
1484 n8->ReplaceInput(1, n53);
1485 n17->ReplaceInput(1, n8);
1486 n18->ReplaceInput(0, n17);
1487 n23->ReplaceInput(0, n18);
1488 n23->ReplaceInput(1, n43);
1489 n26->ReplaceInput(2, n23);
1490 n11->ReplaceInput(1, n26);
1491 n11->ReplaceInput(2, n8);
1492 n16->ReplaceInput(1, n11);
1493 n16->ReplaceInput(2, n6);
1494 op = common_builder.Phi(kMachAnyTagged, 2);
1495 Node* n14 = graph.NewNode(op, nil, nil, nil);
1496 USE(n14);
1497 n14->ReplaceInput(0, n0);
1498 op = common_builder.Phi(kMachAnyTagged, 2);
1499 Node* n55 = graph.NewNode(op, nil, nil, nil);
1500 USE(n55);
1501 n55->ReplaceInput(0, n47);
1502 n55->ReplaceInput(1, n52);
1503 n55->ReplaceInput(2, n53);
1504 n14->ReplaceInput(1, n55);
1505 n14->ReplaceInput(2, n8);
1506 n16->ReplaceInput(3, n14);
1507 n16->ReplaceInput(4, n8);
1508 n20->ReplaceInput(2, n16);
1509 n20->ReplaceInput(3, n18);
1510 n22->ReplaceInput(0, n20);
1511 n22->ReplaceInput(1, n21);
1512 n22->ReplaceInput(2, n6);
1513 n22->ReplaceInput(3, n20);
1514 n22->ReplaceInput(4, n18);
1515 n25->ReplaceInput(0, n22);
1516 n25->ReplaceInput(1, n45);
1517 n25->ReplaceInput(2, n23);
1518 n10->ReplaceInput(1, n25);
1519 n10->ReplaceInput(2, n8);
1520 n56->ReplaceInput(0, n10);
1521 n56->ReplaceInput(1, n13);
1522 n56->ReplaceInput(2, n6);
1523 n56->ReplaceInput(3, n16);
1524 op = common_builder.IfFalse();
1525 Node* n19 = graph.NewNode(op, nil);
1526 USE(n19);
1527 n19->ReplaceInput(0, n17);
1528 n56->ReplaceInput(4, n19);
1529 n57->ReplaceInput(0, n56);
1530 n57->ReplaceInput(1, n56);
1531 n57->ReplaceInput(2, n19);
1532 n58->ReplaceInput(0, n57);
1533
1534 graph.SetStart(n0);
1535 graph.SetEnd(n58);
1536
1537 ComputeAndVerifySchedule(62, &graph);
1538 }
1539
1540
1541 TEST(BuildScheduleSimpleLoopWithCodeMotion) {
1542 HandleAndZoneScope scope;
1543 Isolate* isolate = scope.main_isolate();
1544 Graph graph(scope.main_zone());
1545 CommonOperatorBuilder common_builder(scope.main_zone());
1546 JSOperatorBuilder js_builder(scope.main_zone());
1547 const Operator* op;
1548
1549 Handle<HeapObject> object =
1550 Handle<HeapObject>(isolate->heap()->undefined_value(), isolate);
1551 Unique<HeapObject> unique_constant =
1552 Unique<HeapObject>::CreateUninitialized(object);
1553
1554 // Manually transcripted code for:
1555 // function turbo_fan_test(a, b, c) {
1556 // while (a < b) {
1557 // a += b + c;
1558 // }
1559 // return a;
1560 // }
1561 op = common_builder.Start(0);
1562 Node* n0 = graph.NewNode(op);
1563 USE(n0);
1564 Node* nil = graph.NewNode(common_builder.Dead());
1565 op = common_builder.End();
1566 Node* n22 = graph.NewNode(op, nil);
1567 USE(n22);
1568 op = common_builder.Return();
1569 Node* n21 = graph.NewNode(op, nil, nil, nil);
1570 USE(n21);
1571 op = common_builder.Phi(kMachAnyTagged, 2);
1572 Node* n9 = graph.NewNode(op, nil, nil, nil);
1573 USE(n9);
1574 op = common_builder.Parameter(0);
1575 Node* n2 = graph.NewNode(op, n0);
1576 USE(n2);
1577 n9->ReplaceInput(0, n2);
1578 op = js_builder.Add();
1579 Node* n20 = graph.NewNode(op, nil, nil, nil, nil, nil);
1580 USE(n20);
1581 n20->ReplaceInput(0, n9);
1582 op = &kIntAdd;
1583 Node* n19 = graph.NewNode(op, nil, nil);
1584 USE(n19);
1585 op = common_builder.Phi(kMachAnyTagged, 2);
1586 Node* n10 = graph.NewNode(op, nil, nil, nil);
1587 USE(n10);
1588 op = common_builder.Parameter(0);
1589 Node* n3 = graph.NewNode(op, n0);
1590 USE(n3);
1591 n10->ReplaceInput(0, n3);
1592 n10->ReplaceInput(1, n10);
1593 op = common_builder.Loop(2);
1594 Node* n7 = graph.NewNode(op, nil, nil);
1595 USE(n7);
1596 n7->ReplaceInput(0, n0);
1597 op = common_builder.IfTrue();
1598 Node* n17 = graph.NewNode(op, nil);
1599 USE(n17);
1600 op = common_builder.Branch();
1601 Node* n16 = graph.NewNode(op, nil, nil);
1602 USE(n16);
1603 op = js_builder.ToBoolean();
1604 Node* n15 = graph.NewNode(op, nil, nil, nil, nil);
1605 USE(n15);
1606 op = js_builder.LessThan();
1607 Node* n14 = graph.NewNode(op, nil, nil, nil, nil, nil);
1608 USE(n14);
1609 n14->ReplaceInput(0, n9);
1610 n14->ReplaceInput(1, n10);
1611 op = common_builder.HeapConstant(unique_constant);
1612 Node* n6 = graph.NewNode(op);
1613 USE(n6);
1614 n14->ReplaceInput(2, n6);
1615 op = common_builder.Phi(kMachAnyTagged, 2);
1616 Node* n12 = graph.NewNode(op, nil, nil, nil);
1617 USE(n12);
1618 n12->ReplaceInput(0, n0);
1619 n12->ReplaceInput(1, n20);
1620 n12->ReplaceInput(2, n7);
1621 n14->ReplaceInput(3, n12);
1622 n14->ReplaceInput(4, n7);
1623 n15->ReplaceInput(0, n14);
1624 n15->ReplaceInput(1, n6);
1625 n15->ReplaceInput(2, n14);
1626 n15->ReplaceInput(3, n7);
1627 n16->ReplaceInput(0, n15);
1628 n16->ReplaceInput(1, n7);
1629 n17->ReplaceInput(0, n16);
1630 n7->ReplaceInput(1, n17);
1631 n10->ReplaceInput(2, n7);
1632 n19->ReplaceInput(0, n2);
1633 op = common_builder.Phi(kMachAnyTagged, 2);
1634 Node* n11 = graph.NewNode(op, nil, nil, nil);
1635 USE(n11);
1636 op = common_builder.Parameter(0);
1637 Node* n4 = graph.NewNode(op, n0);
1638 USE(n4);
1639 n11->ReplaceInput(0, n4);
1640 n11->ReplaceInput(1, n11);
1641 n11->ReplaceInput(2, n7);
1642 n19->ReplaceInput(1, n3);
1643 n20->ReplaceInput(1, n19);
1644 n20->ReplaceInput(2, n6);
1645 n20->ReplaceInput(3, n19);
1646 n20->ReplaceInput(4, n17);
1647 n9->ReplaceInput(1, n20);
1648 n9->ReplaceInput(2, n7);
1649 n21->ReplaceInput(0, n9);
1650 n21->ReplaceInput(1, n15);
1651 op = common_builder.IfFalse();
1652 Node* n18 = graph.NewNode(op, nil);
1653 USE(n18);
1654 n18->ReplaceInput(0, n16);
1655 n21->ReplaceInput(2, n18);
1656 n22->ReplaceInput(0, n21);
1657
1658 graph.SetStart(n0);
1659 graph.SetEnd(n22);
1660
1661 Schedule* schedule = ComputeAndVerifySchedule(19, &graph);
1662 // Make sure the integer-only add gets hoisted to a different block that the
1663 // JSAdd.
1664 CHECK(schedule->block(n19) != schedule->block(n20));
1665 }
1666
1667
1668 #if V8_TURBOFAN_TARGET
1669
1670 static Node* CreateDiamond(Graph* graph, CommonOperatorBuilder* common,
1671 Node* cond) {
1672 Node* tv = graph->NewNode(common->Int32Constant(6));
1673 Node* fv = graph->NewNode(common->Int32Constant(7));
1674 Node* br = graph->NewNode(common->Branch(), cond, graph->start());
1675 Node* t = graph->NewNode(common->IfTrue(), br);
1676 Node* f = graph->NewNode(common->IfFalse(), br);
1677 Node* m = graph->NewNode(common->Merge(2), t, f);
1678 Node* phi = graph->NewNode(common->Phi(kMachAnyTagged, 2), tv, fv, m);
1679 return phi;
1680 }
1681
1682
1683 TEST(FloatingDiamond1) {
1684 HandleAndZoneScope scope;
1685 Graph graph(scope.main_zone());
1686 CommonOperatorBuilder common(scope.main_zone());
1687
1688 Node* start = graph.NewNode(common.Start(1));
1689 graph.SetStart(start);
1690
1691 Node* p0 = graph.NewNode(common.Parameter(0), start);
1692 Node* d1 = CreateDiamond(&graph, &common, p0);
1693 Node* ret = graph.NewNode(common.Return(), d1, start, start);
1694 Node* end = graph.NewNode(common.End(), ret, start);
1695
1696 graph.SetEnd(end);
1697
1698 ComputeAndVerifySchedule(13, &graph);
1699 }
1700
1701
1702 TEST(FloatingDiamond2) {
1703 HandleAndZoneScope scope;
1704 Graph graph(scope.main_zone());
1705 CommonOperatorBuilder common(scope.main_zone());
1706
1707 Node* start = graph.NewNode(common.Start(2));
1708 graph.SetStart(start);
1709
1710 Node* p0 = graph.NewNode(common.Parameter(0), start);
1711 Node* p1 = graph.NewNode(common.Parameter(1), start);
1712 Node* d1 = CreateDiamond(&graph, &common, p0);
1713 Node* d2 = CreateDiamond(&graph, &common, p1);
1714 Node* add = graph.NewNode(&kIntAdd, d1, d2);
1715 Node* ret = graph.NewNode(common.Return(), add, start, start);
1716 Node* end = graph.NewNode(common.End(), ret, start);
1717
1718 graph.SetEnd(end);
1719
1720 ComputeAndVerifySchedule(24, &graph);
1721 }
1722
1723
1724 TEST(FloatingDiamond3) {
1725 HandleAndZoneScope scope;
1726 Graph graph(scope.main_zone());
1727 CommonOperatorBuilder common(scope.main_zone());
1728
1729 Node* start = graph.NewNode(common.Start(2));
1730 graph.SetStart(start);
1731
1732 Node* p0 = graph.NewNode(common.Parameter(0), start);
1733 Node* p1 = graph.NewNode(common.Parameter(1), start);
1734 Node* d1 = CreateDiamond(&graph, &common, p0);
1735 Node* d2 = CreateDiamond(&graph, &common, p1);
1736 Node* add = graph.NewNode(&kIntAdd, d1, d2);
1737 Node* d3 = CreateDiamond(&graph, &common, add);
1738 Node* ret = graph.NewNode(common.Return(), d3, start, start);
1739 Node* end = graph.NewNode(common.End(), ret, start);
1740
1741 graph.SetEnd(end);
1742
1743 ComputeAndVerifySchedule(33, &graph);
1744 }
1745
1746
1747 TEST(NestedFloatingDiamonds) {
1748 HandleAndZoneScope scope;
1749 Graph graph(scope.main_zone());
1750 CommonOperatorBuilder common(scope.main_zone());
1751 SimplifiedOperatorBuilder simplified(scope.main_zone());
1752
1753 Node* start = graph.NewNode(common.Start(2));
1754 graph.SetStart(start);
1755
1756 Node* p0 = graph.NewNode(common.Parameter(0), start);
1757
1758 Node* fv = graph.NewNode(common.Int32Constant(7));
1759 Node* br = graph.NewNode(common.Branch(), p0, graph.start());
1760 Node* t = graph.NewNode(common.IfTrue(), br);
1761 Node* f = graph.NewNode(common.IfFalse(), br);
1762
1763 Node* map = graph.NewNode(
1764 simplified.LoadElement(AccessBuilder::ForFixedArrayElement()), p0, p0, p0,
1765 start, f);
1766 Node* br1 = graph.NewNode(common.Branch(), map, graph.start());
1767 Node* t1 = graph.NewNode(common.IfTrue(), br1);
1768 Node* f1 = graph.NewNode(common.IfFalse(), br1);
1769 Node* m1 = graph.NewNode(common.Merge(2), t1, f1);
1770 Node* ttrue = graph.NewNode(common.Int32Constant(1));
1771 Node* ffalse = graph.NewNode(common.Int32Constant(0));
1772 Node* phi1 = graph.NewNode(common.Phi(kMachAnyTagged, 2), ttrue, ffalse, m1);
1773
1774
1775 Node* m = graph.NewNode(common.Merge(2), t, f);
1776 Node* phi = graph.NewNode(common.Phi(kMachAnyTagged, 2), fv, phi1, m);
1777 Node* ephi1 = graph.NewNode(common.EffectPhi(2), start, map, m);
1778
1779 Node* ret = graph.NewNode(common.Return(), phi, ephi1, start);
1780 Node* end = graph.NewNode(common.End(), ret, start);
1781
1782 graph.SetEnd(end);
1783
1784 ComputeAndVerifySchedule(23, &graph);
1785 }
1786
1787
1788 TEST(NestedFloatingDiamondWithChain) {
1789 HandleAndZoneScope scope;
1790 Graph graph(scope.main_zone());
1791 CommonOperatorBuilder common(scope.main_zone());
1792
1793 Node* start = graph.NewNode(common.Start(2));
1794 graph.SetStart(start);
1795
1796 Node* p0 = graph.NewNode(common.Parameter(0), start);
1797 Node* p1 = graph.NewNode(common.Parameter(1), start);
1798 Node* c = graph.NewNode(common.Int32Constant(7));
1799
1800 Node* brA1 = graph.NewNode(common.Branch(), p0, graph.start());
1801 Node* tA1 = graph.NewNode(common.IfTrue(), brA1);
1802 Node* fA1 = graph.NewNode(common.IfFalse(), brA1);
1803 Node* mA1 = graph.NewNode(common.Merge(2), tA1, fA1);
1804 Node* phiA1 = graph.NewNode(common.Phi(kMachAnyTagged, 2), p0, p1, mA1);
1805
1806 Node* brB1 = graph.NewNode(common.Branch(), p1, graph.start());
1807 Node* tB1 = graph.NewNode(common.IfTrue(), brB1);
1808 Node* fB1 = graph.NewNode(common.IfFalse(), brB1);
1809 Node* mB1 = graph.NewNode(common.Merge(2), tB1, fB1);
1810 Node* phiB1 = graph.NewNode(common.Phi(kMachAnyTagged, 2), p0, p1, mB1);
1811
1812 Node* brA2 = graph.NewNode(common.Branch(), phiB1, mA1);
1813 Node* tA2 = graph.NewNode(common.IfTrue(), brA2);
1814 Node* fA2 = graph.NewNode(common.IfFalse(), brA2);
1815 Node* mA2 = graph.NewNode(common.Merge(2), tA2, fA2);
1816 Node* phiA2 = graph.NewNode(common.Phi(kMachAnyTagged, 2), phiB1, c, mA2);
1817
1818 Node* brB2 = graph.NewNode(common.Branch(), phiA1, mB1);
1819 Node* tB2 = graph.NewNode(common.IfTrue(), brB2);
1820 Node* fB2 = graph.NewNode(common.IfFalse(), brB2);
1821 Node* mB2 = graph.NewNode(common.Merge(2), tB2, fB2);
1822 Node* phiB2 = graph.NewNode(common.Phi(kMachAnyTagged, 2), phiA1, c, mB2);
1823
1824 Node* add = graph.NewNode(&kIntAdd, phiA2, phiB2);
1825 Node* ret = graph.NewNode(common.Return(), add, start, start);
1826 Node* end = graph.NewNode(common.End(), ret, start);
1827
1828 graph.SetEnd(end);
1829
1830 ComputeAndVerifySchedule(35, &graph);
1831 }
1832
1833
1834 TEST(NestedFloatingDiamondWithLoop) {
1835 HandleAndZoneScope scope;
1836 Graph graph(scope.main_zone());
1837 CommonOperatorBuilder common(scope.main_zone());
1838
1839 Node* start = graph.NewNode(common.Start(2));
1840 graph.SetStart(start);
1841
1842 Node* p0 = graph.NewNode(common.Parameter(0), start);
1843
1844 Node* fv = graph.NewNode(common.Int32Constant(7));
1845 Node* br = graph.NewNode(common.Branch(), p0, graph.start());
1846 Node* t = graph.NewNode(common.IfTrue(), br);
1847 Node* f = graph.NewNode(common.IfFalse(), br);
1848
1849 Node* loop = graph.NewNode(common.Loop(2), f, start);
1850 Node* ind = graph.NewNode(common.Phi(kMachAnyTagged, 2), p0, p0, loop);
1851
1852 Node* add = graph.NewNode(&kIntAdd, ind, fv);
1853 Node* br1 = graph.NewNode(common.Branch(), add, loop);
1854 Node* t1 = graph.NewNode(common.IfTrue(), br1);
1855 Node* f1 = graph.NewNode(common.IfFalse(), br1);
1856
1857 loop->ReplaceInput(1, t1); // close loop.
1858 ind->ReplaceInput(1, ind); // close induction variable.
1859
1860 Node* m = graph.NewNode(common.Merge(2), t, f1);
1861 Node* phi = graph.NewNode(common.Phi(kMachAnyTagged, 2), fv, ind, m);
1862
1863 Node* ret = graph.NewNode(common.Return(), phi, start, start);
1864 Node* end = graph.NewNode(common.End(), ret, start);
1865
1866 graph.SetEnd(end);
1867
1868 ComputeAndVerifySchedule(20, &graph);
1869 }
1870
1871
1872 TEST(LoopedFloatingDiamond1) {
1873 HandleAndZoneScope scope;
1874 Graph graph(scope.main_zone());
1875 CommonOperatorBuilder common(scope.main_zone());
1876
1877 Node* start = graph.NewNode(common.Start(2));
1878 graph.SetStart(start);
1879
1880 Node* p0 = graph.NewNode(common.Parameter(0), start);
1881
1882 Node* c = graph.NewNode(common.Int32Constant(7));
1883 Node* loop = graph.NewNode(common.Loop(2), start, start);
1884 Node* ind = graph.NewNode(common.Phi(kMachAnyTagged, 2), p0, p0, loop);
1885 Node* add = graph.NewNode(&kIntAdd, ind, c);
1886
1887 Node* br = graph.NewNode(common.Branch(), add, loop);
1888 Node* t = graph.NewNode(common.IfTrue(), br);
1889 Node* f = graph.NewNode(common.IfFalse(), br);
1890
1891 Node* br1 = graph.NewNode(common.Branch(), p0, graph.start());
1892 Node* t1 = graph.NewNode(common.IfTrue(), br1);
1893 Node* f1 = graph.NewNode(common.IfFalse(), br1);
1894 Node* m1 = graph.NewNode(common.Merge(2), t1, f1);
1895 Node* phi1 = graph.NewNode(common.Phi(kMachAnyTagged, 2), add, p0, m1);
1896
1897 loop->ReplaceInput(1, t); // close loop.
1898 ind->ReplaceInput(1, phi1); // close induction variable.
1899
1900 Node* ret = graph.NewNode(common.Return(), ind, start, f);
1901 Node* end = graph.NewNode(common.End(), ret, f);
1902
1903 graph.SetEnd(end);
1904
1905 ComputeAndVerifySchedule(20, &graph);
1906 }
1907
1908
1909 TEST(LoopedFloatingDiamond2) {
1910 HandleAndZoneScope scope;
1911 Graph graph(scope.main_zone());
1912 CommonOperatorBuilder common(scope.main_zone());
1913
1914 Node* start = graph.NewNode(common.Start(2));
1915 graph.SetStart(start);
1916
1917 Node* p0 = graph.NewNode(common.Parameter(0), start);
1918
1919 Node* c = graph.NewNode(common.Int32Constant(7));
1920 Node* loop = graph.NewNode(common.Loop(2), start, start);
1921 Node* ind = graph.NewNode(common.Phi(kMachAnyTagged, 2), p0, p0, loop);
1922
1923 Node* br1 = graph.NewNode(common.Branch(), p0, graph.start());
1924 Node* t1 = graph.NewNode(common.IfTrue(), br1);
1925 Node* f1 = graph.NewNode(common.IfFalse(), br1);
1926 Node* m1 = graph.NewNode(common.Merge(2), t1, f1);
1927 Node* phi1 = graph.NewNode(common.Phi(kMachAnyTagged, 2), c, ind, m1);
1928
1929 Node* add = graph.NewNode(&kIntAdd, ind, phi1);
1930
1931 Node* br = graph.NewNode(common.Branch(), add, loop);
1932 Node* t = graph.NewNode(common.IfTrue(), br);
1933 Node* f = graph.NewNode(common.IfFalse(), br);
1934
1935 loop->ReplaceInput(1, t); // close loop.
1936 ind->ReplaceInput(1, add); // close induction variable.
1937
1938 Node* ret = graph.NewNode(common.Return(), ind, start, f);
1939 Node* end = graph.NewNode(common.End(), ret, f);
1940
1941 graph.SetEnd(end);
1942
1943 ComputeAndVerifySchedule(20, &graph);
1944 }
1945
1946
1947 TEST(LoopedFloatingDiamond3) {
1948 HandleAndZoneScope scope;
1949 Graph graph(scope.main_zone());
1950 CommonOperatorBuilder common(scope.main_zone());
1951
1952 Node* start = graph.NewNode(common.Start(2));
1953 graph.SetStart(start);
1954
1955 Node* p0 = graph.NewNode(common.Parameter(0), start);
1956
1957 Node* c = graph.NewNode(common.Int32Constant(7));
1958 Node* loop = graph.NewNode(common.Loop(2), start, start);
1959 Node* ind = graph.NewNode(common.Phi(kMachAnyTagged, 2), p0, p0, loop);
1960
1961 Node* br1 = graph.NewNode(common.Branch(), p0, graph.start());
1962 Node* t1 = graph.NewNode(common.IfTrue(), br1);
1963 Node* f1 = graph.NewNode(common.IfFalse(), br1);
1964
1965 Node* loop1 = graph.NewNode(common.Loop(2), t1, start);
1966 Node* ind1 = graph.NewNode(common.Phi(kMachAnyTagged, 2), p0, p0, loop);
1967
1968 Node* add1 = graph.NewNode(&kIntAdd, ind1, c);
1969 Node* br2 = graph.NewNode(common.Branch(), add1, loop1);
1970 Node* t2 = graph.NewNode(common.IfTrue(), br2);
1971 Node* f2 = graph.NewNode(common.IfFalse(), br2);
1972
1973 loop1->ReplaceInput(1, t2); // close inner loop.
1974 ind1->ReplaceInput(1, ind1); // close inner induction variable.
1975
1976 Node* m1 = graph.NewNode(common.Merge(2), f1, f2);
1977 Node* phi1 = graph.NewNode(common.Phi(kMachAnyTagged, 2), c, ind1, m1);
1978
1979 Node* add = graph.NewNode(&kIntAdd, ind, phi1);
1980
1981 Node* br = graph.NewNode(common.Branch(), add, loop);
1982 Node* t = graph.NewNode(common.IfTrue(), br);
1983 Node* f = graph.NewNode(common.IfFalse(), br);
1984
1985 loop->ReplaceInput(1, t); // close loop.
1986 ind->ReplaceInput(1, add); // close induction variable.
1987
1988 Node* ret = graph.NewNode(common.Return(), ind, start, f);
1989 Node* end = graph.NewNode(common.End(), ret, f);
1990
1991 graph.SetEnd(end);
1992
1993 ComputeAndVerifySchedule(28, &graph);
1994 }
1995
1996
1997 TEST(PhisPushedDownToDifferentBranches) {
1998 HandleAndZoneScope scope;
1999 Graph graph(scope.main_zone());
2000 CommonOperatorBuilder common(scope.main_zone());
2001
2002 Node* start = graph.NewNode(common.Start(2));
2003 graph.SetStart(start);
2004
2005 Node* p0 = graph.NewNode(common.Parameter(0), start);
2006 Node* p1 = graph.NewNode(common.Parameter(1), start);
2007
2008 Node* v1 = graph.NewNode(common.Int32Constant(1));
2009 Node* v2 = graph.NewNode(common.Int32Constant(2));
2010 Node* v3 = graph.NewNode(common.Int32Constant(3));
2011 Node* v4 = graph.NewNode(common.Int32Constant(4));
2012 Node* br = graph.NewNode(common.Branch(), p0, graph.start());
2013 Node* t = graph.NewNode(common.IfTrue(), br);
2014 Node* f = graph.NewNode(common.IfFalse(), br);
2015 Node* m = graph.NewNode(common.Merge(2), t, f);
2016 Node* phi = graph.NewNode(common.Phi(kMachAnyTagged, 2), v1, v2, m);
2017 Node* phi2 = graph.NewNode(common.Phi(kMachAnyTagged, 2), v3, v4, m);
2018
2019 Node* br2 = graph.NewNode(common.Branch(), p1, graph.start());
2020 Node* t2 = graph.NewNode(common.IfTrue(), br2);
2021 Node* f2 = graph.NewNode(common.IfFalse(), br2);
2022 Node* m2 = graph.NewNode(common.Merge(2), t2, f2);
2023 Node* phi3 = graph.NewNode(common.Phi(kMachAnyTagged, 2), phi, phi2, m2);
2024
2025 Node* ret = graph.NewNode(common.Return(), phi3, start, start);
2026 Node* end = graph.NewNode(common.End(), ret, start);
2027
2028 graph.SetEnd(end);
2029
2030 ComputeAndVerifySchedule(24, &graph);
2031 }
2032
2033
2034 TEST(BranchHintTrue) {
2035 HandleAndZoneScope scope;
2036 Graph graph(scope.main_zone());
2037 CommonOperatorBuilder common(scope.main_zone());
2038
2039 Node* start = graph.NewNode(common.Start(1));
2040 graph.SetStart(start);
2041
2042 Node* p0 = graph.NewNode(common.Parameter(0), start);
2043 Node* tv = graph.NewNode(common.Int32Constant(6));
2044 Node* fv = graph.NewNode(common.Int32Constant(7));
2045 Node* br = graph.NewNode(common.Branch(BranchHint::kTrue), p0, start);
2046 Node* t = graph.NewNode(common.IfTrue(), br);
2047 Node* f = graph.NewNode(common.IfFalse(), br);
2048 Node* m = graph.NewNode(common.Merge(2), t, f);
2049 Node* phi = graph.NewNode(common.Phi(kMachAnyTagged, 2), tv, fv, m);
2050 Node* ret = graph.NewNode(common.Return(), phi, start, start);
2051 Node* end = graph.NewNode(common.End(), ret, start);
2052
2053 graph.SetEnd(end);
2054
2055 Schedule* schedule = ComputeAndVerifySchedule(13, &graph);
2056 // Make sure the false block is marked as deferred.
2057 CHECK(!schedule->block(t)->deferred());
2058 CHECK(schedule->block(f)->deferred());
2059 }
2060
2061
2062 TEST(BranchHintFalse) {
2063 HandleAndZoneScope scope;
2064 Graph graph(scope.main_zone());
2065 CommonOperatorBuilder common(scope.main_zone());
2066
2067 Node* start = graph.NewNode(common.Start(1));
2068 graph.SetStart(start);
2069
2070 Node* p0 = graph.NewNode(common.Parameter(0), start);
2071 Node* tv = graph.NewNode(common.Int32Constant(6));
2072 Node* fv = graph.NewNode(common.Int32Constant(7));
2073 Node* br = graph.NewNode(common.Branch(BranchHint::kFalse), p0, start);
2074 Node* t = graph.NewNode(common.IfTrue(), br);
2075 Node* f = graph.NewNode(common.IfFalse(), br);
2076 Node* m = graph.NewNode(common.Merge(2), t, f);
2077 Node* phi = graph.NewNode(common.Phi(kMachAnyTagged, 2), tv, fv, m);
2078 Node* ret = graph.NewNode(common.Return(), phi, start, start);
2079 Node* end = graph.NewNode(common.End(), ret, start);
2080
2081 graph.SetEnd(end);
2082
2083 Schedule* schedule = ComputeAndVerifySchedule(13, &graph);
2084 // Make sure the true block is marked as deferred.
2085 CHECK(schedule->block(t)->deferred());
2086 CHECK(!schedule->block(f)->deferred());
2087 }
2088
2089
2090 TEST(ScheduleTerminate) {
2091 HandleAndZoneScope scope;
2092 Graph graph(scope.main_zone());
2093 CommonOperatorBuilder common(scope.main_zone());
2094
2095 Node* start = graph.NewNode(common.Start(1));
2096 graph.SetStart(start);
2097
2098 Node* loop = graph.NewNode(common.Loop(2), start, start);
2099 loop->ReplaceInput(1, loop); // self loop, NTL.
2100
2101 Node* effect = graph.NewNode(common.EffectPhi(1), start, loop);
2102 effect->ReplaceInput(0, effect);
2103
2104 Node* terminate = graph.NewNode(common.Terminate(1), effect, loop);
2105 Node* end = graph.NewNode(common.End(), terminate);
2106
2107 graph.SetEnd(end);
2108
2109 Schedule* schedule = ComputeAndVerifySchedule(6, &graph);
2110 BasicBlock* block = schedule->block(loop);
2111 CHECK_NE(NULL, loop);
2112 CHECK_EQ(block, schedule->block(effect));
2113 CHECK_GE(block->rpo_number(), 0);
2114 }
2115
2116 #endif
OLDNEW
« no previous file with comments | « test/cctest/cctest.gyp ('k') | test/unittests/compiler/scheduler-unittest.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698