deps/v8/test/unittests/compiler/scheduler-unittest.cc

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