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

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

Powered by Google App Engine
This is Rietveld 408576698