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/source-position.h" 17 #include "src/compiler/verifier.h" 18 #include "test/unittests/compiler/compiler-test-utils.h" 19 #include "test/unittests/test-utils.h" 20 #include "testing/gmock/include/gmock/gmock.h" 21 22 using testing::AnyOf; 23 24 namespace v8 { 25 namespace internal { 26 namespace compiler { 27 28 class SchedulerTest : public TestWithIsolateAndZone { 29 public: 30 SchedulerTest() 31 : graph_(zone()), common_(zone()), simplified_(zone()), js_(zone()) {} 32 33 Schedule* ComputeAndVerifySchedule(size_t expected) { 34 if (FLAG_trace_turbo) { 35 OFStream os(stdout); 36 SourcePositionTable table(graph()); 37 os << AsJSON(*graph(), &table); 38 } 39 40 Schedule* schedule = 41 Scheduler::ComputeSchedule(zone(), graph(), Scheduler::kSplitNodes); 42 43 if (FLAG_trace_turbo_scheduler) { 44 OFStream os(stdout); 45 os << *schedule << std::endl; 46 } 47 ScheduleVerifier::Run(schedule); 48 EXPECT_EQ(expected, GetScheduledNodeCount(schedule)); 49 return schedule; 50 } 51 52 size_t GetScheduledNodeCount(const Schedule* schedule) { 53 size_t node_count = 0; 54 for (auto block : *schedule->rpo_order()) { 55 node_count += block->NodeCount(); 56 if (block->control() != BasicBlock::kNone) ++node_count; 57 } 58 return node_count; 59 } 60 61 Graph* graph() { return &graph_; } 62 CommonOperatorBuilder* common() { return &common_; } 63 SimplifiedOperatorBuilder* simplified() { return &simplified_; } 64 JSOperatorBuilder* js() { return &js_; } 65 66 private: 67 Graph graph_; 68 CommonOperatorBuilder common_; 69 SimplifiedOperatorBuilder simplified_; 70 JSOperatorBuilder js_; 71 }; 72 73 74 class SchedulerRPOTest : public SchedulerTest { 75 public: 76 SchedulerRPOTest() {} 77 78 // TODO(titzer): pull RPO tests out to their own file. 79 void CheckRPONumbers(BasicBlockVector* order, size_t expected, 80 bool loops_allowed) { 81 CHECK(expected == order->size()); 82 for (int i = 0; i < static_cast<int>(order->size()); i++) { 83 CHECK(order->at(i)->rpo_number() == i); 84 if (!loops_allowed) { 85 CHECK(!order->at(i)->loop_end()); 86 CHECK(!order->at(i)->loop_header()); 87 } 88 } 89 } 90 91 void CheckLoop(BasicBlockVector* order, BasicBlock** blocks, int body_size) { 92 BasicBlock* header = blocks[0]; 93 BasicBlock* end = header->loop_end(); 94 CHECK(end); 95 CHECK_GT(end->rpo_number(), 0); 96 CHECK_EQ(body_size, end->rpo_number() - header->rpo_number()); 97 for (int i = 0; i < body_size; i++) { 98 CHECK_GE(blocks[i]->rpo_number(), header->rpo_number()); 99 CHECK_LT(blocks[i]->rpo_number(), end->rpo_number()); 100 CHECK(header->LoopContains(blocks[i])); 101 CHECK(header->IsLoopHeader() || blocks[i]->loop_header() == header); 102 } 103 if (header->rpo_number() > 0) { 104 CHECK_NE(order->at(header->rpo_number() - 1)->loop_header(), header); 105 } 106 if (end->rpo_number() < static_cast<int>(order->size())) { 107 CHECK_NE(order->at(end->rpo_number())->loop_header(), header); 108 } 109 } 110 111 struct TestLoop { 112 int count; 113 BasicBlock** nodes; 114 BasicBlock* header() { return nodes[0]; } 115 BasicBlock* last() { return nodes[count - 1]; } 116 ~TestLoop() { delete[] nodes; } 117 }; 118 119 TestLoop* CreateLoop(Schedule* schedule, int count) { 120 TestLoop* loop = new TestLoop(); 121 loop->count = count; 122 loop->nodes = new BasicBlock* [count]; 123 for (int i = 0; i < count; i++) { 124 loop->nodes[i] = schedule->NewBasicBlock(); 125 if (i > 0) { 126 schedule->AddSuccessorForTesting(loop->nodes[i - 1], loop->nodes[i]); 127 } 128 } 129 schedule->AddSuccessorForTesting(loop->nodes[count - 1], loop->nodes[0]); 130 return loop; 131 } 132 }; 133 134 135 namespace { 136 137 const Operator kHeapConstant(IrOpcode::kHeapConstant, Operator::kPure, 138 "HeapConstant", 0, 0, 0, 1, 0, 0); 139 const Operator kIntAdd(IrOpcode::kInt32Add, Operator::kPure, "Int32Add", 2, 0, 140 0, 1, 0, 0); 141 const Operator kMockCall(IrOpcode::kCall, Operator::kNoProperties, "MockCall", 142 0, 0, 1, 1, 1, 2); 143 const Operator kMockTailCall(IrOpcode::kTailCall, Operator::kNoProperties, 144 "MockTailCall", 1, 1, 1, 0, 0, 1); 145 146 } // namespace 147 148 149 // ----------------------------------------------------------------------------- 150 // Special reverse-post-order block ordering. 151 152 153 TEST_F(SchedulerRPOTest, Degenerate1) { 154 Schedule schedule(zone()); 155 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 156 CheckRPONumbers(order, 1, false); 157 EXPECT_EQ(schedule.start(), order->at(0)); 158 } 159 160 161 TEST_F(SchedulerRPOTest, Degenerate2) { 162 Schedule schedule(zone()); 163 164 schedule.AddGoto(schedule.start(), schedule.end()); 165 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 166 CheckRPONumbers(order, 2, false); 167 EXPECT_EQ(schedule.start(), order->at(0)); 168 EXPECT_EQ(schedule.end(), order->at(1)); 169 } 170 171 172 TEST_F(SchedulerRPOTest, Line) { 173 for (int i = 0; i < 10; i++) { 174 Schedule schedule(zone()); 175 176 BasicBlock* last = schedule.start(); 177 for (int j = 0; j < i; j++) { 178 BasicBlock* block = schedule.NewBasicBlock(); 179 block->set_deferred(i & 1); 180 schedule.AddGoto(last, block); 181 last = block; 182 } 183 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 184 CheckRPONumbers(order, 1 + i, false); 185 186 for (size_t i = 0; i < schedule.BasicBlockCount(); i++) { 187 BasicBlock* block = schedule.GetBlockById(BasicBlock::Id::FromSize(i)); 188 if (block->rpo_number() >= 0 && block->SuccessorCount() == 1) { 189 EXPECT_EQ(block->rpo_number() + 1, block->SuccessorAt(0)->rpo_number()); 190 } 191 } 192 } 193 } 194 195 196 TEST_F(SchedulerRPOTest, SelfLoop) { 197 Schedule schedule(zone()); 198 schedule.AddSuccessorForTesting(schedule.start(), schedule.start()); 199 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 200 CheckRPONumbers(order, 1, true); 201 BasicBlock* loop[] = {schedule.start()}; 202 CheckLoop(order, loop, 1); 203 } 204 205 206 TEST_F(SchedulerRPOTest, EntryLoop) { 207 Schedule schedule(zone()); 208 BasicBlock* body = schedule.NewBasicBlock(); 209 schedule.AddSuccessorForTesting(schedule.start(), body); 210 schedule.AddSuccessorForTesting(body, schedule.start()); 211 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 212 CheckRPONumbers(order, 2, true); 213 BasicBlock* loop[] = {schedule.start(), body}; 214 CheckLoop(order, loop, 2); 215 } 216 217 218 TEST_F(SchedulerRPOTest, EndLoop) { 219 Schedule schedule(zone()); 220 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 2)); 221 schedule.AddSuccessorForTesting(schedule.start(), loop1->header()); 222 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 223 CheckRPONumbers(order, 3, true); 224 CheckLoop(order, loop1->nodes, loop1->count); 225 } 226 227 228 TEST_F(SchedulerRPOTest, EndLoopNested) { 229 Schedule schedule(zone()); 230 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 2)); 231 schedule.AddSuccessorForTesting(schedule.start(), loop1->header()); 232 schedule.AddSuccessorForTesting(loop1->last(), schedule.start()); 233 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 234 CheckRPONumbers(order, 3, true); 235 CheckLoop(order, loop1->nodes, loop1->count); 236 } 237 238 239 TEST_F(SchedulerRPOTest, Diamond) { 240 Schedule schedule(zone()); 241 242 BasicBlock* A = schedule.start(); 243 BasicBlock* B = schedule.NewBasicBlock(); 244 BasicBlock* C = schedule.NewBasicBlock(); 245 BasicBlock* D = schedule.end(); 246 247 schedule.AddSuccessorForTesting(A, B); 248 schedule.AddSuccessorForTesting(A, C); 249 schedule.AddSuccessorForTesting(B, D); 250 schedule.AddSuccessorForTesting(C, D); 251 252 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 253 CheckRPONumbers(order, 4, false); 254 255 EXPECT_EQ(0, A->rpo_number()); 256 EXPECT_THAT(B->rpo_number(), AnyOf(1, 2)); 257 EXPECT_THAT(C->rpo_number(), AnyOf(1, 2)); 258 EXPECT_EQ(3, D->rpo_number()); 259 } 260 261 262 TEST_F(SchedulerRPOTest, Loop1) { 263 Schedule schedule(zone()); 264 265 BasicBlock* A = schedule.start(); 266 BasicBlock* B = schedule.NewBasicBlock(); 267 BasicBlock* C = schedule.NewBasicBlock(); 268 BasicBlock* D = schedule.end(); 269 270 schedule.AddSuccessorForTesting(A, B); 271 schedule.AddSuccessorForTesting(B, C); 272 schedule.AddSuccessorForTesting(C, B); 273 schedule.AddSuccessorForTesting(C, D); 274 275 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 276 CheckRPONumbers(order, 4, true); 277 BasicBlock* loop[] = {B, C}; 278 CheckLoop(order, loop, 2); 279 } 280 281 282 TEST_F(SchedulerRPOTest, Loop2) { 283 Schedule schedule(zone()); 284 285 BasicBlock* A = schedule.start(); 286 BasicBlock* B = schedule.NewBasicBlock(); 287 BasicBlock* C = schedule.NewBasicBlock(); 288 BasicBlock* D = schedule.end(); 289 290 schedule.AddSuccessorForTesting(A, B); 291 schedule.AddSuccessorForTesting(B, C); 292 schedule.AddSuccessorForTesting(C, B); 293 schedule.AddSuccessorForTesting(B, D); 294 295 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 296 CheckRPONumbers(order, 4, true); 297 BasicBlock* loop[] = {B, C}; 298 CheckLoop(order, loop, 2); 299 } 300 301 302 TEST_F(SchedulerRPOTest, LoopN) { 303 for (int i = 0; i < 11; i++) { 304 Schedule schedule(zone()); 305 BasicBlock* A = schedule.start(); 306 BasicBlock* B = schedule.NewBasicBlock(); 307 BasicBlock* C = schedule.NewBasicBlock(); 308 BasicBlock* D = schedule.NewBasicBlock(); 309 BasicBlock* E = schedule.NewBasicBlock(); 310 BasicBlock* F = schedule.NewBasicBlock(); 311 BasicBlock* G = schedule.end(); 312 313 schedule.AddSuccessorForTesting(A, B); 314 schedule.AddSuccessorForTesting(B, C); 315 schedule.AddSuccessorForTesting(C, D); 316 schedule.AddSuccessorForTesting(D, E); 317 schedule.AddSuccessorForTesting(E, F); 318 schedule.AddSuccessorForTesting(F, B); 319 schedule.AddSuccessorForTesting(B, G); 320 321 // Throw in extra backedges from time to time. 322 if (i == 1) schedule.AddSuccessorForTesting(B, B); 323 if (i == 2) schedule.AddSuccessorForTesting(C, B); 324 if (i == 3) schedule.AddSuccessorForTesting(D, B); 325 if (i == 4) schedule.AddSuccessorForTesting(E, B); 326 if (i == 5) schedule.AddSuccessorForTesting(F, B); 327 328 // Throw in extra loop exits from time to time. 329 if (i == 6) schedule.AddSuccessorForTesting(B, G); 330 if (i == 7) schedule.AddSuccessorForTesting(C, G); 331 if (i == 8) schedule.AddSuccessorForTesting(D, G); 332 if (i == 9) schedule.AddSuccessorForTesting(E, G); 333 if (i == 10) schedule.AddSuccessorForTesting(F, G); 334 335 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 336 CheckRPONumbers(order, 7, true); 337 BasicBlock* loop[] = {B, C, D, E, F}; 338 CheckLoop(order, loop, 5); 339 } 340 } 341 342 343 TEST_F(SchedulerRPOTest, LoopNest1) { 344 Schedule schedule(zone()); 345 346 BasicBlock* A = schedule.start(); 347 BasicBlock* B = schedule.NewBasicBlock(); 348 BasicBlock* C = schedule.NewBasicBlock(); 349 BasicBlock* D = schedule.NewBasicBlock(); 350 BasicBlock* E = schedule.NewBasicBlock(); 351 BasicBlock* F = schedule.end(); 352 353 schedule.AddSuccessorForTesting(A, B); 354 schedule.AddSuccessorForTesting(B, C); 355 schedule.AddSuccessorForTesting(C, D); 356 schedule.AddSuccessorForTesting(D, C); 357 schedule.AddSuccessorForTesting(D, E); 358 schedule.AddSuccessorForTesting(E, B); 359 schedule.AddSuccessorForTesting(E, F); 360 361 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 362 CheckRPONumbers(order, 6, true); 363 BasicBlock* loop1[] = {B, C, D, E}; 364 CheckLoop(order, loop1, 4); 365 366 BasicBlock* loop2[] = {C, D}; 367 CheckLoop(order, loop2, 2); 368 } 369 370 371 TEST_F(SchedulerRPOTest, LoopNest2) { 372 Schedule schedule(zone()); 373 374 BasicBlock* A = schedule.start(); 375 BasicBlock* B = schedule.NewBasicBlock(); 376 BasicBlock* C = schedule.NewBasicBlock(); 377 BasicBlock* D = schedule.NewBasicBlock(); 378 BasicBlock* E = schedule.NewBasicBlock(); 379 BasicBlock* F = schedule.NewBasicBlock(); 380 BasicBlock* G = schedule.NewBasicBlock(); 381 BasicBlock* H = schedule.end(); 382 383 schedule.AddSuccessorForTesting(A, B); 384 schedule.AddSuccessorForTesting(B, C); 385 schedule.AddSuccessorForTesting(C, D); 386 schedule.AddSuccessorForTesting(D, E); 387 schedule.AddSuccessorForTesting(E, F); 388 schedule.AddSuccessorForTesting(F, G); 389 schedule.AddSuccessorForTesting(G, H); 390 391 schedule.AddSuccessorForTesting(E, D); 392 schedule.AddSuccessorForTesting(F, C); 393 schedule.AddSuccessorForTesting(G, B); 394 395 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 396 CheckRPONumbers(order, 8, true); 397 BasicBlock* loop1[] = {B, C, D, E, F, G}; 398 CheckLoop(order, loop1, 6); 399 400 BasicBlock* loop2[] = {C, D, E, F}; 401 CheckLoop(order, loop2, 4); 402 403 BasicBlock* loop3[] = {D, E}; 404 CheckLoop(order, loop3, 2); 405 } 406 407 408 TEST_F(SchedulerRPOTest, LoopFollow1) { 409 Schedule schedule(zone()); 410 411 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 1)); 412 base::SmartPointer<TestLoop> loop2(CreateLoop(&schedule, 1)); 413 414 BasicBlock* A = schedule.start(); 415 BasicBlock* E = schedule.end(); 416 417 schedule.AddSuccessorForTesting(A, loop1->header()); 418 schedule.AddSuccessorForTesting(loop1->header(), loop2->header()); 419 schedule.AddSuccessorForTesting(loop2->last(), E); 420 421 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 422 423 EXPECT_EQ(schedule.BasicBlockCount(), order->size()); 424 CheckLoop(order, loop1->nodes, loop1->count); 425 CheckLoop(order, loop2->nodes, loop2->count); 426 } 427 428 429 TEST_F(SchedulerRPOTest, LoopFollow2) { 430 Schedule schedule(zone()); 431 432 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 1)); 433 base::SmartPointer<TestLoop> loop2(CreateLoop(&schedule, 1)); 434 435 BasicBlock* A = schedule.start(); 436 BasicBlock* S = schedule.NewBasicBlock(); 437 BasicBlock* E = schedule.end(); 438 439 schedule.AddSuccessorForTesting(A, loop1->header()); 440 schedule.AddSuccessorForTesting(loop1->header(), S); 441 schedule.AddSuccessorForTesting(S, loop2->header()); 442 schedule.AddSuccessorForTesting(loop2->last(), E); 443 444 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 445 446 EXPECT_EQ(schedule.BasicBlockCount(), order->size()); 447 CheckLoop(order, loop1->nodes, loop1->count); 448 CheckLoop(order, loop2->nodes, loop2->count); 449 } 450 451 452 TEST_F(SchedulerRPOTest, LoopFollowN) { 453 for (int size = 1; size < 5; size++) { 454 for (int exit = 0; exit < size; exit++) { 455 Schedule schedule(zone()); 456 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size)); 457 base::SmartPointer<TestLoop> loop2(CreateLoop(&schedule, size)); 458 BasicBlock* A = schedule.start(); 459 BasicBlock* E = schedule.end(); 460 461 schedule.AddSuccessorForTesting(A, loop1->header()); 462 schedule.AddSuccessorForTesting(loop1->nodes[exit], loop2->header()); 463 schedule.AddSuccessorForTesting(loop2->nodes[exit], E); 464 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 465 466 EXPECT_EQ(schedule.BasicBlockCount(), order->size()); 467 CheckLoop(order, loop1->nodes, loop1->count); 468 CheckLoop(order, loop2->nodes, loop2->count); 469 } 470 } 471 } 472 473 474 TEST_F(SchedulerRPOTest, NestedLoopFollow1) { 475 Schedule schedule(zone()); 476 477 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 1)); 478 base::SmartPointer<TestLoop> loop2(CreateLoop(&schedule, 1)); 479 480 BasicBlock* A = schedule.start(); 481 BasicBlock* B = schedule.NewBasicBlock(); 482 BasicBlock* C = schedule.NewBasicBlock(); 483 BasicBlock* E = schedule.end(); 484 485 schedule.AddSuccessorForTesting(A, B); 486 schedule.AddSuccessorForTesting(B, loop1->header()); 487 schedule.AddSuccessorForTesting(loop1->header(), loop2->header()); 488 schedule.AddSuccessorForTesting(loop2->last(), C); 489 schedule.AddSuccessorForTesting(C, E); 490 schedule.AddSuccessorForTesting(C, B); 491 492 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 493 494 EXPECT_EQ(schedule.BasicBlockCount(), order->size()); 495 CheckLoop(order, loop1->nodes, loop1->count); 496 CheckLoop(order, loop2->nodes, loop2->count); 497 498 BasicBlock* loop3[] = {B, loop1->nodes[0], loop2->nodes[0], C}; 499 CheckLoop(order, loop3, 4); 500 } 501 502 503 TEST_F(SchedulerRPOTest, LoopBackedges1) { 504 int size = 8; 505 for (int i = 0; i < size; i++) { 506 for (int j = 0; j < size; j++) { 507 Schedule schedule(zone()); 508 BasicBlock* A = schedule.start(); 509 BasicBlock* E = schedule.end(); 510 511 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size)); 512 schedule.AddSuccessorForTesting(A, loop1->header()); 513 schedule.AddSuccessorForTesting(loop1->last(), E); 514 515 schedule.AddSuccessorForTesting(loop1->nodes[i], loop1->header()); 516 schedule.AddSuccessorForTesting(loop1->nodes[j], E); 517 518 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 519 CheckRPONumbers(order, schedule.BasicBlockCount(), true); 520 CheckLoop(order, loop1->nodes, loop1->count); 521 } 522 } 523 } 524 525 526 TEST_F(SchedulerRPOTest, LoopOutedges1) { 527 int size = 8; 528 for (int i = 0; i < size; i++) { 529 for (int j = 0; j < size; j++) { 530 Schedule schedule(zone()); 531 BasicBlock* A = schedule.start(); 532 BasicBlock* D = schedule.NewBasicBlock(); 533 BasicBlock* E = schedule.end(); 534 535 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size)); 536 schedule.AddSuccessorForTesting(A, loop1->header()); 537 schedule.AddSuccessorForTesting(loop1->last(), E); 538 539 schedule.AddSuccessorForTesting(loop1->nodes[i], loop1->header()); 540 schedule.AddSuccessorForTesting(loop1->nodes[j], D); 541 schedule.AddSuccessorForTesting(D, E); 542 543 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 544 CheckRPONumbers(order, schedule.BasicBlockCount(), true); 545 CheckLoop(order, loop1->nodes, loop1->count); 546 } 547 } 548 } 549 550 551 TEST_F(SchedulerRPOTest, LoopOutedges2) { 552 int size = 8; 553 for (int i = 0; i < size; i++) { 554 Schedule schedule(zone()); 555 BasicBlock* A = schedule.start(); 556 BasicBlock* E = schedule.end(); 557 558 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size)); 559 schedule.AddSuccessorForTesting(A, loop1->header()); 560 schedule.AddSuccessorForTesting(loop1->last(), E); 561 562 for (int j = 0; j < size; j++) { 563 BasicBlock* O = schedule.NewBasicBlock(); 564 schedule.AddSuccessorForTesting(loop1->nodes[j], O); 565 schedule.AddSuccessorForTesting(O, E); 566 } 567 568 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 569 CheckRPONumbers(order, schedule.BasicBlockCount(), true); 570 CheckLoop(order, loop1->nodes, loop1->count); 571 } 572 } 573 574 575 TEST_F(SchedulerRPOTest, LoopOutloops1) { 576 int size = 8; 577 for (int i = 0; i < size; i++) { 578 Schedule schedule(zone()); 579 BasicBlock* A = schedule.start(); 580 BasicBlock* E = schedule.end(); 581 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size)); 582 schedule.AddSuccessorForTesting(A, loop1->header()); 583 schedule.AddSuccessorForTesting(loop1->last(), E); 584 585 TestLoop** loopN = new TestLoop* [size]; 586 for (int j = 0; j < size; j++) { 587 loopN[j] = CreateLoop(&schedule, 2); 588 schedule.AddSuccessorForTesting(loop1->nodes[j], loopN[j]->header()); 589 schedule.AddSuccessorForTesting(loopN[j]->last(), E); 590 } 591 592 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 593 CheckRPONumbers(order, schedule.BasicBlockCount(), true); 594 CheckLoop(order, loop1->nodes, loop1->count); 595 596 for (int j = 0; j < size; j++) { 597 CheckLoop(order, loopN[j]->nodes, loopN[j]->count); 598 delete loopN[j]; 599 } 600 delete[] loopN; 601 } 602 } 603 604 605 TEST_F(SchedulerRPOTest, LoopMultibackedge) { 606 Schedule schedule(zone()); 607 608 BasicBlock* A = schedule.start(); 609 BasicBlock* B = schedule.NewBasicBlock(); 610 BasicBlock* C = schedule.NewBasicBlock(); 611 BasicBlock* D = schedule.NewBasicBlock(); 612 BasicBlock* E = schedule.NewBasicBlock(); 613 614 schedule.AddSuccessorForTesting(A, B); 615 schedule.AddSuccessorForTesting(B, C); 616 schedule.AddSuccessorForTesting(B, D); 617 schedule.AddSuccessorForTesting(B, E); 618 schedule.AddSuccessorForTesting(C, B); 619 schedule.AddSuccessorForTesting(D, B); 620 schedule.AddSuccessorForTesting(E, B); 621 622 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); 623 CheckRPONumbers(order, 5, true); 624 625 BasicBlock* loop1[] = {B, C, D, E}; 626 CheckLoop(order, loop1, 4); 627 } 628 629 630 // ----------------------------------------------------------------------------- 631 // Graph end-to-end scheduling. 632 633 634 TEST_F(SchedulerTest, BuildScheduleEmpty) { 635 graph()->SetStart(graph()->NewNode(common()->Start(0))); 636 graph()->SetEnd(graph()->NewNode(common()->End(1), graph()->start())); 637 USE(Scheduler::ComputeSchedule(zone(), graph(), Scheduler::kNoFlags)); 638 } 639 640 641 TEST_F(SchedulerTest, BuildScheduleOneParameter) { 642 graph()->SetStart(graph()->NewNode(common()->Start(0))); 643 644 Node* p1 = graph()->NewNode(common()->Parameter(0), graph()->start()); 645 Node* ret = graph()->NewNode(common()->Return(), p1, graph()->start(), 646 graph()->start()); 647 648 graph()->SetEnd(graph()->NewNode(common()->End(1), ret)); 649 650 USE(Scheduler::ComputeSchedule(zone(), graph(), Scheduler::kNoFlags)); 651 } 652 653 654 namespace { 655 656 Node* CreateDiamond(Graph* graph, CommonOperatorBuilder* common, Node* cond) { 657 Node* tv = graph->NewNode(common->Int32Constant(6)); 658 Node* fv = graph->NewNode(common->Int32Constant(7)); 659 Node* br = graph->NewNode(common->Branch(), cond, graph->start()); 660 Node* t = graph->NewNode(common->IfTrue(), br); 661 Node* f = graph->NewNode(common->IfFalse(), br); 662 Node* m = graph->NewNode(common->Merge(2), t, f); 663 Node* phi = 664 graph->NewNode(common->Phi(MachineRepresentation::kTagged, 2), tv, fv, m); 665 return phi; 666 } 667 668 } // namespace 669 670 671 TARGET_TEST_F(SchedulerTest, FloatingDiamond1) { 672 Node* start = graph()->NewNode(common()->Start(1)); 673 graph()->SetStart(start); 674 675 Node* p0 = graph()->NewNode(common()->Parameter(0), start); 676 Node* d1 = CreateDiamond(graph(), common(), p0); 677 Node* ret = graph()->NewNode(common()->Return(), d1, start, start); 678 Node* end = graph()->NewNode(common()->End(1), ret); 679 680 graph()->SetEnd(end); 681 682 ComputeAndVerifySchedule(13); 683 } 684 685 686 TARGET_TEST_F(SchedulerTest, FloatingDiamond2) { 687 Node* start = graph()->NewNode(common()->Start(2)); 688 graph()->SetStart(start); 689 690 Node* p0 = graph()->NewNode(common()->Parameter(0), start); 691 Node* p1 = graph()->NewNode(common()->Parameter(1), start); 692 Node* d1 = CreateDiamond(graph(), common(), p0); 693 Node* d2 = CreateDiamond(graph(), common(), p1); 694 Node* add = graph()->NewNode(&kIntAdd, d1, d2); 695 Node* ret = graph()->NewNode(common()->Return(), add, start, start); 696 Node* end = graph()->NewNode(common()->End(1), ret); 697 698 graph()->SetEnd(end); 699 700 ComputeAndVerifySchedule(24); 701 } 702 703 704 TARGET_TEST_F(SchedulerTest, FloatingDiamond3) { 705 Node* start = graph()->NewNode(common()->Start(2)); 706 graph()->SetStart(start); 707 708 Node* p0 = graph()->NewNode(common()->Parameter(0), start); 709 Node* p1 = graph()->NewNode(common()->Parameter(1), start); 710 Node* d1 = CreateDiamond(graph(), common(), p0); 711 Node* d2 = CreateDiamond(graph(), common(), p1); 712 Node* add = graph()->NewNode(&kIntAdd, d1, d2); 713 Node* d3 = CreateDiamond(graph(), common(), add); 714 Node* ret = graph()->NewNode(common()->Return(), d3, start, start); 715 Node* end = graph()->NewNode(common()->End(1), ret); 716 717 graph()->SetEnd(end); 718 719 ComputeAndVerifySchedule(33); 720 } 721 722 723 TARGET_TEST_F(SchedulerTest, NestedFloatingDiamonds) { 724 Node* start = graph()->NewNode(common()->Start(2)); 725 graph()->SetStart(start); 726 727 Node* p0 = graph()->NewNode(common()->Parameter(0), start); 728 729 Node* fv = graph()->NewNode(common()->Int32Constant(7)); 730 Node* br = graph()->NewNode(common()->Branch(), p0, graph()->start()); 731 Node* t = graph()->NewNode(common()->IfTrue(), br); 732 Node* f = graph()->NewNode(common()->IfFalse(), br); 733 734 Node* map = graph()->NewNode( 735 simplified()->LoadElement(AccessBuilder::ForFixedArrayElement()), p0, p0, 736 start, f); 737 Node* br1 = graph()->NewNode(common()->Branch(), map, graph()->start()); 738 Node* t1 = graph()->NewNode(common()->IfTrue(), br1); 739 Node* f1 = graph()->NewNode(common()->IfFalse(), br1); 740 Node* m1 = graph()->NewNode(common()->Merge(2), t1, f1); 741 Node* ttrue = graph()->NewNode(common()->Int32Constant(1)); 742 Node* ffalse = graph()->NewNode(common()->Int32Constant(0)); 743 Node* phi1 = graph()->NewNode( 744 common()->Phi(MachineRepresentation::kTagged, 2), ttrue, ffalse, m1); 745 746 747 Node* m = graph()->NewNode(common()->Merge(2), t, f); 748 Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2), 749 fv, phi1, m); 750 Node* ephi1 = graph()->NewNode(common()->EffectPhi(2), start, map, m); 751 752 Node* ret = graph()->NewNode(common()->Return(), phi, ephi1, start); 753 Node* end = graph()->NewNode(common()->End(1), ret); 754 755 graph()->SetEnd(end); 756 757 ComputeAndVerifySchedule(23); 758 } 759 760 761 TARGET_TEST_F(SchedulerTest, NestedFloatingDiamondWithChain) { 762 Node* start = graph()->NewNode(common()->Start(2)); 763 graph()->SetStart(start); 764 765 Node* p0 = graph()->NewNode(common()->Parameter(0), start); 766 Node* p1 = graph()->NewNode(common()->Parameter(1), start); 767 Node* c = graph()->NewNode(common()->Int32Constant(7)); 768 769 Node* brA1 = graph()->NewNode(common()->Branch(), p0, graph()->start()); 770 Node* tA1 = graph()->NewNode(common()->IfTrue(), brA1); 771 Node* fA1 = graph()->NewNode(common()->IfFalse(), brA1); 772 Node* mA1 = graph()->NewNode(common()->Merge(2), tA1, fA1); 773 Node* phiA1 = graph()->NewNode( 774 common()->Phi(MachineRepresentation::kTagged, 2), p0, p1, mA1); 775 776 Node* brB1 = graph()->NewNode(common()->Branch(), p1, graph()->start()); 777 Node* tB1 = graph()->NewNode(common()->IfTrue(), brB1); 778 Node* fB1 = graph()->NewNode(common()->IfFalse(), brB1); 779 Node* mB1 = graph()->NewNode(common()->Merge(2), tB1, fB1); 780 Node* phiB1 = graph()->NewNode( 781 common()->Phi(MachineRepresentation::kTagged, 2), p0, p1, mB1); 782 783 Node* brA2 = graph()->NewNode(common()->Branch(), phiB1, mA1); 784 Node* tA2 = graph()->NewNode(common()->IfTrue(), brA2); 785 Node* fA2 = graph()->NewNode(common()->IfFalse(), brA2); 786 Node* mA2 = graph()->NewNode(common()->Merge(2), tA2, fA2); 787 Node* phiA2 = graph()->NewNode( 788 common()->Phi(MachineRepresentation::kTagged, 2), phiB1, c, mA2); 789 790 Node* brB2 = graph()->NewNode(common()->Branch(), phiA1, mB1); 791 Node* tB2 = graph()->NewNode(common()->IfTrue(), brB2); 792 Node* fB2 = graph()->NewNode(common()->IfFalse(), brB2); 793 Node* mB2 = graph()->NewNode(common()->Merge(2), tB2, fB2); 794 Node* phiB2 = graph()->NewNode( 795 common()->Phi(MachineRepresentation::kTagged, 2), phiA1, c, mB2); 796 797 Node* add = graph()->NewNode(&kIntAdd, phiA2, phiB2); 798 Node* ret = graph()->NewNode(common()->Return(), add, start, start); 799 Node* end = graph()->NewNode(common()->End(1), ret); 800 801 graph()->SetEnd(end); 802 803 ComputeAndVerifySchedule(36); 804 } 805 806 807 TARGET_TEST_F(SchedulerTest, NestedFloatingDiamondWithLoop) { 808 Node* start = graph()->NewNode(common()->Start(2)); 809 graph()->SetStart(start); 810 811 Node* p0 = graph()->NewNode(common()->Parameter(0), start); 812 813 Node* fv = graph()->NewNode(common()->Int32Constant(7)); 814 Node* br = graph()->NewNode(common()->Branch(), p0, graph()->start()); 815 Node* t = graph()->NewNode(common()->IfTrue(), br); 816 Node* f = graph()->NewNode(common()->IfFalse(), br); 817 818 Node* loop = graph()->NewNode(common()->Loop(2), f, start); 819 Node* ind = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2), 820 p0, p0, loop); 821 822 Node* add = graph()->NewNode(&kIntAdd, ind, fv); 823 Node* br1 = graph()->NewNode(common()->Branch(), add, loop); 824 Node* t1 = graph()->NewNode(common()->IfTrue(), br1); 825 Node* f1 = graph()->NewNode(common()->IfFalse(), br1); 826 827 loop->ReplaceInput(1, t1); // close loop. 828 ind->ReplaceInput(1, ind); // close induction variable. 829 830 Node* m = graph()->NewNode(common()->Merge(2), t, f1); 831 Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2), 832 fv, ind, m); 833 834 Node* ret = graph()->NewNode(common()->Return(), phi, start, start); 835 Node* end = graph()->NewNode(common()->End(1), ret); 836 837 graph()->SetEnd(end); 838 839 ComputeAndVerifySchedule(20); 840 } 841 842 843 TARGET_TEST_F(SchedulerTest, LoopedFloatingDiamond1) { 844 Node* start = graph()->NewNode(common()->Start(2)); 845 graph()->SetStart(start); 846 847 Node* p0 = graph()->NewNode(common()->Parameter(0), start); 848 849 Node* c = graph()->NewNode(common()->Int32Constant(7)); 850 Node* loop = graph()->NewNode(common()->Loop(2), start, start); 851 Node* ind = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2), 852 p0, p0, loop); 853 Node* add = graph()->NewNode(&kIntAdd, ind, c); 854 855 Node* br = graph()->NewNode(common()->Branch(), add, loop); 856 Node* t = graph()->NewNode(common()->IfTrue(), br); 857 Node* f = graph()->NewNode(common()->IfFalse(), br); 858 859 Node* br1 = graph()->NewNode(common()->Branch(), p0, graph()->start()); 860 Node* t1 = graph()->NewNode(common()->IfTrue(), br1); 861 Node* f1 = graph()->NewNode(common()->IfFalse(), br1); 862 Node* m1 = graph()->NewNode(common()->Merge(2), t1, f1); 863 Node* phi1 = graph()->NewNode( 864 common()->Phi(MachineRepresentation::kTagged, 2), add, p0, m1); 865 866 loop->ReplaceInput(1, t); // close loop. 867 ind->ReplaceInput(1, phi1); // close induction variable. 868 869 Node* ret = graph()->NewNode(common()->Return(), ind, start, f); 870 Node* end = graph()->NewNode(common()->End(2), ret, f); 871 872 graph()->SetEnd(end); 873 874 ComputeAndVerifySchedule(20); 875 } 876 877 878 TARGET_TEST_F(SchedulerTest, LoopedFloatingDiamond2) { 879 Node* start = graph()->NewNode(common()->Start(2)); 880 graph()->SetStart(start); 881 882 Node* p0 = graph()->NewNode(common()->Parameter(0), start); 883 884 Node* c = graph()->NewNode(common()->Int32Constant(7)); 885 Node* loop = graph()->NewNode(common()->Loop(2), start, start); 886 Node* ind = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2), 887 p0, p0, loop); 888 889 Node* br1 = graph()->NewNode(common()->Branch(), p0, graph()->start()); 890 Node* t1 = graph()->NewNode(common()->IfTrue(), br1); 891 Node* f1 = graph()->NewNode(common()->IfFalse(), br1); 892 Node* m1 = graph()->NewNode(common()->Merge(2), t1, f1); 893 Node* phi1 = graph()->NewNode( 894 common()->Phi(MachineRepresentation::kTagged, 2), c, ind, m1); 895 896 Node* add = graph()->NewNode(&kIntAdd, ind, phi1); 897 898 Node* br = graph()->NewNode(common()->Branch(), add, loop); 899 Node* t = graph()->NewNode(common()->IfTrue(), br); 900 Node* f = graph()->NewNode(common()->IfFalse(), br); 901 902 loop->ReplaceInput(1, t); // close loop. 903 ind->ReplaceInput(1, add); // close induction variable. 904 905 Node* ret = graph()->NewNode(common()->Return(), ind, start, f); 906 Node* end = graph()->NewNode(common()->End(2), ret, f); 907 908 graph()->SetEnd(end); 909 910 ComputeAndVerifySchedule(20); 911 } 912 913 914 TARGET_TEST_F(SchedulerTest, LoopedFloatingDiamond3) { 915 Node* start = graph()->NewNode(common()->Start(2)); 916 graph()->SetStart(start); 917 918 Node* p0 = graph()->NewNode(common()->Parameter(0), start); 919 920 Node* c = graph()->NewNode(common()->Int32Constant(7)); 921 Node* loop = graph()->NewNode(common()->Loop(2), start, start); 922 Node* ind = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2), 923 p0, p0, loop); 924 925 Node* br1 = graph()->NewNode(common()->Branch(), p0, graph()->start()); 926 Node* t1 = graph()->NewNode(common()->IfTrue(), br1); 927 Node* f1 = graph()->NewNode(common()->IfFalse(), br1); 928 929 Node* loop1 = graph()->NewNode(common()->Loop(2), t1, start); 930 Node* ind1 = graph()->NewNode( 931 common()->Phi(MachineRepresentation::kTagged, 2), p0, p0, loop); 932 933 Node* add1 = graph()->NewNode(&kIntAdd, ind1, c); 934 Node* br2 = graph()->NewNode(common()->Branch(), add1, loop1); 935 Node* t2 = graph()->NewNode(common()->IfTrue(), br2); 936 Node* f2 = graph()->NewNode(common()->IfFalse(), br2); 937 938 loop1->ReplaceInput(1, t2); // close inner loop. 939 ind1->ReplaceInput(1, ind1); // close inner induction variable. 940 941 Node* m1 = graph()->NewNode(common()->Merge(2), f1, f2); 942 Node* phi1 = graph()->NewNode( 943 common()->Phi(MachineRepresentation::kTagged, 2), c, ind1, m1); 944 945 Node* add = graph()->NewNode(&kIntAdd, ind, phi1); 946 947 Node* br = graph()->NewNode(common()->Branch(), add, loop); 948 Node* t = graph()->NewNode(common()->IfTrue(), br); 949 Node* f = graph()->NewNode(common()->IfFalse(), br); 950 951 loop->ReplaceInput(1, t); // close loop. 952 ind->ReplaceInput(1, add); // close induction variable. 953 954 Node* ret = graph()->NewNode(common()->Return(), ind, start, f); 955 Node* end = graph()->NewNode(common()->End(2), ret, f); 956 957 graph()->SetEnd(end); 958 959 ComputeAndVerifySchedule(28); 960 } 961 962 963 TARGET_TEST_F(SchedulerTest, PhisPushedDownToDifferentBranches) { 964 Node* start = graph()->NewNode(common()->Start(2)); 965 graph()->SetStart(start); 966 967 Node* p0 = graph()->NewNode(common()->Parameter(0), start); 968 Node* p1 = graph()->NewNode(common()->Parameter(1), start); 969 970 Node* v1 = graph()->NewNode(common()->Int32Constant(1)); 971 Node* v2 = graph()->NewNode(common()->Int32Constant(2)); 972 Node* v3 = graph()->NewNode(common()->Int32Constant(3)); 973 Node* v4 = graph()->NewNode(common()->Int32Constant(4)); 974 Node* br = graph()->NewNode(common()->Branch(), p0, graph()->start()); 975 Node* t = graph()->NewNode(common()->IfTrue(), br); 976 Node* f = graph()->NewNode(common()->IfFalse(), br); 977 Node* m = graph()->NewNode(common()->Merge(2), t, f); 978 Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2), 979 v1, v2, m); 980 Node* phi2 = graph()->NewNode( 981 common()->Phi(MachineRepresentation::kTagged, 2), v3, v4, m); 982 983 Node* br2 = graph()->NewNode(common()->Branch(), p1, graph()->start()); 984 Node* t2 = graph()->NewNode(common()->IfTrue(), br2); 985 Node* f2 = graph()->NewNode(common()->IfFalse(), br2); 986 Node* m2 = graph()->NewNode(common()->Merge(2), t2, f2); 987 Node* phi3 = graph()->NewNode( 988 common()->Phi(MachineRepresentation::kTagged, 2), phi, phi2, m2); 989 990 Node* ret = graph()->NewNode(common()->Return(), phi3, start, start); 991 Node* end = graph()->NewNode(common()->End(1), ret); 992 993 graph()->SetEnd(end); 994 995 ComputeAndVerifySchedule(24); 996 } 997 998 999 TARGET_TEST_F(SchedulerTest, BranchHintTrue) { 1000 Node* start = graph()->NewNode(common()->Start(1)); 1001 graph()->SetStart(start); 1002 1003 Node* p0 = graph()->NewNode(common()->Parameter(0), start); 1004 Node* tv = graph()->NewNode(common()->Int32Constant(6)); 1005 Node* fv = graph()->NewNode(common()->Int32Constant(7)); 1006 Node* br = graph()->NewNode(common()->Branch(BranchHint::kTrue), p0, start); 1007 Node* t = graph()->NewNode(common()->IfTrue(), br); 1008 Node* f = graph()->NewNode(common()->IfFalse(), br); 1009 Node* m = graph()->NewNode(common()->Merge(2), t, f); 1010 Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2), 1011 tv, fv, m); 1012 Node* ret = graph()->NewNode(common()->Return(), phi, start, start); 1013 Node* end = graph()->NewNode(common()->End(1), ret); 1014 1015 graph()->SetEnd(end); 1016 1017 Schedule* schedule = ComputeAndVerifySchedule(13); 1018 // Make sure the false block is marked as deferred. 1019 EXPECT_FALSE(schedule->block(t)->deferred()); 1020 EXPECT_TRUE(schedule->block(f)->deferred()); 1021 } 1022 1023 1024 TARGET_TEST_F(SchedulerTest, BranchHintFalse) { 1025 Node* start = graph()->NewNode(common()->Start(1)); 1026 graph()->SetStart(start); 1027 1028 Node* p0 = graph()->NewNode(common()->Parameter(0), start); 1029 Node* tv = graph()->NewNode(common()->Int32Constant(6)); 1030 Node* fv = graph()->NewNode(common()->Int32Constant(7)); 1031 Node* br = graph()->NewNode(common()->Branch(BranchHint::kFalse), p0, start); 1032 Node* t = graph()->NewNode(common()->IfTrue(), br); 1033 Node* f = graph()->NewNode(common()->IfFalse(), br); 1034 Node* m = graph()->NewNode(common()->Merge(2), t, f); 1035 Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2), 1036 tv, fv, m); 1037 Node* ret = graph()->NewNode(common()->Return(), phi, start, start); 1038 Node* end = graph()->NewNode(common()->End(1), ret); 1039 1040 graph()->SetEnd(end); 1041 1042 Schedule* schedule = ComputeAndVerifySchedule(13); 1043 // Make sure the true block is marked as deferred. 1044 EXPECT_TRUE(schedule->block(t)->deferred()); 1045 EXPECT_FALSE(schedule->block(f)->deferred()); 1046 } 1047 1048 1049 TARGET_TEST_F(SchedulerTest, CallException) { 1050 Node* start = graph()->NewNode(common()->Start(1)); 1051 graph()->SetStart(start); 1052 1053 Node* p0 = graph()->NewNode(common()->Parameter(0), start); 1054 Node* c1 = graph()->NewNode(&kMockCall, start); 1055 Node* ok1 = graph()->NewNode(common()->IfSuccess(), c1); 1056 Node* ex1 = graph()->NewNode( 1057 common()->IfException(IfExceptionHint::kLocallyUncaught), c1, c1); 1058 Node* c2 = graph()->NewNode(&kMockCall, ok1); 1059 Node* ok2 = graph()->NewNode(common()->IfSuccess(), c2); 1060 Node* ex2 = graph()->NewNode( 1061 common()->IfException(IfExceptionHint::kLocallyUncaught), c2, c2); 1062 Node* hdl = graph()->NewNode(common()->Merge(2), ex1, ex2); 1063 Node* m = graph()->NewNode(common()->Merge(2), ok2, hdl); 1064 Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2), 1065 c2, p0, m); 1066 Node* ret = graph()->NewNode(common()->Return(), phi, start, m); 1067 Node* end = graph()->NewNode(common()->End(1), ret); 1068 1069 graph()->SetEnd(end); 1070 1071 Schedule* schedule = ComputeAndVerifySchedule(17); 1072 // Make sure the exception blocks as well as the handler are deferred. 1073 EXPECT_TRUE(schedule->block(ex1)->deferred()); 1074 EXPECT_TRUE(schedule->block(ex2)->deferred()); 1075 EXPECT_TRUE(schedule->block(hdl)->deferred()); 1076 EXPECT_FALSE(schedule->block(m)->deferred()); 1077 } 1078 1079 1080 TARGET_TEST_F(SchedulerTest, TailCall) { 1081 Node* start = graph()->NewNode(common()->Start(1)); 1082 graph()->SetStart(start); 1083 1084 Node* p0 = graph()->NewNode(common()->Parameter(0), start); 1085 Node* call = graph()->NewNode(&kMockTailCall, p0, start, start); 1086 Node* end = graph()->NewNode(common()->End(1), call); 1087 1088 graph()->SetEnd(end); 1089 1090 ComputeAndVerifySchedule(4); 1091 } 1092 1093 1094 TARGET_TEST_F(SchedulerTest, Switch) { 1095 Node* start = graph()->NewNode(common()->Start(1)); 1096 graph()->SetStart(start); 1097 1098 Node* p0 = graph()->NewNode(common()->Parameter(0), start); 1099 Node* sw = graph()->NewNode(common()->Switch(3), p0, start); 1100 Node* c0 = graph()->NewNode(common()->IfValue(0), sw); 1101 Node* v0 = graph()->NewNode(common()->Int32Constant(11)); 1102 Node* c1 = graph()->NewNode(common()->IfValue(1), sw); 1103 Node* v1 = graph()->NewNode(common()->Int32Constant(22)); 1104 Node* d = graph()->NewNode(common()->IfDefault(), sw); 1105 Node* vd = graph()->NewNode(common()->Int32Constant(33)); 1106 Node* m = graph()->NewNode(common()->Merge(3), c0, c1, d); 1107 Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 3), 1108 v0, v1, vd, m); 1109 Node* ret = graph()->NewNode(common()->Return(), phi, start, m); 1110 Node* end = graph()->NewNode(common()->End(1), ret); 1111 1112 graph()->SetEnd(end); 1113 1114 ComputeAndVerifySchedule(16); 1115 } 1116 1117 1118 TARGET_TEST_F(SchedulerTest, FloatingSwitch) { 1119 Node* start = graph()->NewNode(common()->Start(1)); 1120 graph()->SetStart(start); 1121 1122 Node* p0 = graph()->NewNode(common()->Parameter(0), start); 1123 Node* sw = graph()->NewNode(common()->Switch(3), p0, start); 1124 Node* c0 = graph()->NewNode(common()->IfValue(0), sw); 1125 Node* v0 = graph()->NewNode(common()->Int32Constant(11)); 1126 Node* c1 = graph()->NewNode(common()->IfValue(1), sw); 1127 Node* v1 = graph()->NewNode(common()->Int32Constant(22)); 1128 Node* d = graph()->NewNode(common()->IfDefault(), sw); 1129 Node* vd = graph()->NewNode(common()->Int32Constant(33)); 1130 Node* m = graph()->NewNode(common()->Merge(3), c0, c1, d); 1131 Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 3), 1132 v0, v1, vd, m); 1133 Node* ret = graph()->NewNode(common()->Return(), phi, start, start); 1134 Node* end = graph()->NewNode(common()->End(1), ret); 1135 1136 graph()->SetEnd(end); 1137 1138 ComputeAndVerifySchedule(16); 1139 } 1140 1141 1142 TARGET_TEST_F(SchedulerTest, Terminate) { 1143 Node* start = graph()->NewNode(common()->Start(1)); 1144 graph()->SetStart(start); 1145 1146 Node* loop = graph()->NewNode(common()->Loop(2), start, start); 1147 loop->ReplaceInput(1, loop); // self loop, NTL. 1148 1149 Node* effect = graph()->NewNode(common()->EffectPhi(2), start, start, loop); 1150 effect->ReplaceInput(1, effect); // self loop. 1151 1152 Node* terminate = graph()->NewNode(common()->Terminate(), effect, loop); 1153 Node* end = graph()->NewNode(common()->End(1), terminate); 1154 graph()->SetEnd(end); 1155 1156 Schedule* schedule = ComputeAndVerifySchedule(6); 1157 BasicBlock* block = schedule->block(loop); 1158 EXPECT_EQ(block, schedule->block(effect)); 1159 EXPECT_GE(block->rpo_number(), 0); 1160 } 1161 1162 } // namespace compiler 1163 } // namespace internal 1164 } // namespace v8 1165
