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