src/v8/test/cctest/compiler/test-scheduler.cc

   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