| OLD | NEW |
| 1 // Copyright 2015 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include <memory> |
| 6 |
| 5 #include "src/compiler/schedule.h" | 7 #include "src/compiler/schedule.h" |
| 6 #include "src/compiler/scheduler.h" | 8 #include "src/compiler/scheduler.h" |
| 7 #include "test/unittests/compiler/compiler-test-utils.h" | 9 #include "test/unittests/compiler/compiler-test-utils.h" |
| 8 #include "test/unittests/test-utils.h" | 10 #include "test/unittests/test-utils.h" |
| 9 #include "testing/gmock/include/gmock/gmock.h" | 11 #include "testing/gmock/include/gmock/gmock.h" |
| 10 | 12 |
| 11 using testing::AnyOf; | 13 using testing::AnyOf; |
| 12 | 14 |
| 13 namespace v8 { | 15 namespace v8 { |
| 14 namespace internal { | 16 namespace internal { |
| (...skipping 113 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 128 schedule.AddSuccessorForTesting(schedule.start(), body); | 130 schedule.AddSuccessorForTesting(schedule.start(), body); |
| 129 schedule.AddSuccessorForTesting(body, schedule.start()); | 131 schedule.AddSuccessorForTesting(body, schedule.start()); |
| 130 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); | 132 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); |
| 131 CheckRPONumbers(order, 2, true); | 133 CheckRPONumbers(order, 2, true); |
| 132 BasicBlock* loop[] = {schedule.start(), body}; | 134 BasicBlock* loop[] = {schedule.start(), body}; |
| 133 CheckLoop(order, loop, 2); | 135 CheckLoop(order, loop, 2); |
| 134 } | 136 } |
| 135 | 137 |
| 136 TEST_F(SchedulerRPOTest, EndLoop) { | 138 TEST_F(SchedulerRPOTest, EndLoop) { |
| 137 Schedule schedule(zone()); | 139 Schedule schedule(zone()); |
| 138 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 2)); | 140 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, 2)); |
| 139 schedule.AddSuccessorForTesting(schedule.start(), loop1->header()); | 141 schedule.AddSuccessorForTesting(schedule.start(), loop1->header()); |
| 140 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); | 142 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); |
| 141 CheckRPONumbers(order, 3, true); | 143 CheckRPONumbers(order, 3, true); |
| 142 CheckLoop(order, loop1->nodes, loop1->count); | 144 CheckLoop(order, loop1->nodes, loop1->count); |
| 143 } | 145 } |
| 144 | 146 |
| 145 TEST_F(SchedulerRPOTest, EndLoopNested) { | 147 TEST_F(SchedulerRPOTest, EndLoopNested) { |
| 146 Schedule schedule(zone()); | 148 Schedule schedule(zone()); |
| 147 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 2)); | 149 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, 2)); |
| 148 schedule.AddSuccessorForTesting(schedule.start(), loop1->header()); | 150 schedule.AddSuccessorForTesting(schedule.start(), loop1->header()); |
| 149 schedule.AddSuccessorForTesting(loop1->last(), schedule.start()); | 151 schedule.AddSuccessorForTesting(loop1->last(), schedule.start()); |
| 150 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); | 152 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); |
| 151 CheckRPONumbers(order, 3, true); | 153 CheckRPONumbers(order, 3, true); |
| 152 CheckLoop(order, loop1->nodes, loop1->count); | 154 CheckLoop(order, loop1->nodes, loop1->count); |
| 153 } | 155 } |
| 154 | 156 |
| 155 TEST_F(SchedulerRPOTest, Diamond) { | 157 TEST_F(SchedulerRPOTest, Diamond) { |
| 156 Schedule schedule(zone()); | 158 Schedule schedule(zone()); |
| 157 | 159 |
| (...skipping 153 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 311 BasicBlock* loop2[] = {C, D, E, F}; | 313 BasicBlock* loop2[] = {C, D, E, F}; |
| 312 CheckLoop(order, loop2, 4); | 314 CheckLoop(order, loop2, 4); |
| 313 | 315 |
| 314 BasicBlock* loop3[] = {D, E}; | 316 BasicBlock* loop3[] = {D, E}; |
| 315 CheckLoop(order, loop3, 2); | 317 CheckLoop(order, loop3, 2); |
| 316 } | 318 } |
| 317 | 319 |
| 318 TEST_F(SchedulerRPOTest, LoopFollow1) { | 320 TEST_F(SchedulerRPOTest, LoopFollow1) { |
| 319 Schedule schedule(zone()); | 321 Schedule schedule(zone()); |
| 320 | 322 |
| 321 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 1)); | 323 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, 1)); |
| 322 base::SmartPointer<TestLoop> loop2(CreateLoop(&schedule, 1)); | 324 std::unique_ptr<TestLoop> loop2(CreateLoop(&schedule, 1)); |
| 323 | 325 |
| 324 BasicBlock* A = schedule.start(); | 326 BasicBlock* A = schedule.start(); |
| 325 BasicBlock* E = schedule.end(); | 327 BasicBlock* E = schedule.end(); |
| 326 | 328 |
| 327 schedule.AddSuccessorForTesting(A, loop1->header()); | 329 schedule.AddSuccessorForTesting(A, loop1->header()); |
| 328 schedule.AddSuccessorForTesting(loop1->header(), loop2->header()); | 330 schedule.AddSuccessorForTesting(loop1->header(), loop2->header()); |
| 329 schedule.AddSuccessorForTesting(loop2->last(), E); | 331 schedule.AddSuccessorForTesting(loop2->last(), E); |
| 330 | 332 |
| 331 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); | 333 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); |
| 332 | 334 |
| 333 EXPECT_EQ(schedule.BasicBlockCount(), order->size()); | 335 EXPECT_EQ(schedule.BasicBlockCount(), order->size()); |
| 334 CheckLoop(order, loop1->nodes, loop1->count); | 336 CheckLoop(order, loop1->nodes, loop1->count); |
| 335 CheckLoop(order, loop2->nodes, loop2->count); | 337 CheckLoop(order, loop2->nodes, loop2->count); |
| 336 } | 338 } |
| 337 | 339 |
| 338 TEST_F(SchedulerRPOTest, LoopFollow2) { | 340 TEST_F(SchedulerRPOTest, LoopFollow2) { |
| 339 Schedule schedule(zone()); | 341 Schedule schedule(zone()); |
| 340 | 342 |
| 341 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 1)); | 343 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, 1)); |
| 342 base::SmartPointer<TestLoop> loop2(CreateLoop(&schedule, 1)); | 344 std::unique_ptr<TestLoop> loop2(CreateLoop(&schedule, 1)); |
| 343 | 345 |
| 344 BasicBlock* A = schedule.start(); | 346 BasicBlock* A = schedule.start(); |
| 345 BasicBlock* S = schedule.NewBasicBlock(); | 347 BasicBlock* S = schedule.NewBasicBlock(); |
| 346 BasicBlock* E = schedule.end(); | 348 BasicBlock* E = schedule.end(); |
| 347 | 349 |
| 348 schedule.AddSuccessorForTesting(A, loop1->header()); | 350 schedule.AddSuccessorForTesting(A, loop1->header()); |
| 349 schedule.AddSuccessorForTesting(loop1->header(), S); | 351 schedule.AddSuccessorForTesting(loop1->header(), S); |
| 350 schedule.AddSuccessorForTesting(S, loop2->header()); | 352 schedule.AddSuccessorForTesting(S, loop2->header()); |
| 351 schedule.AddSuccessorForTesting(loop2->last(), E); | 353 schedule.AddSuccessorForTesting(loop2->last(), E); |
| 352 | 354 |
| 353 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); | 355 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); |
| 354 | 356 |
| 355 EXPECT_EQ(schedule.BasicBlockCount(), order->size()); | 357 EXPECT_EQ(schedule.BasicBlockCount(), order->size()); |
| 356 CheckLoop(order, loop1->nodes, loop1->count); | 358 CheckLoop(order, loop1->nodes, loop1->count); |
| 357 CheckLoop(order, loop2->nodes, loop2->count); | 359 CheckLoop(order, loop2->nodes, loop2->count); |
| 358 } | 360 } |
| 359 | 361 |
| 360 TEST_F(SchedulerRPOTest, LoopFollowN) { | 362 TEST_F(SchedulerRPOTest, LoopFollowN) { |
| 361 for (int size = 1; size < 5; size++) { | 363 for (int size = 1; size < 5; size++) { |
| 362 for (int exit = 0; exit < size; exit++) { | 364 for (int exit = 0; exit < size; exit++) { |
| 363 Schedule schedule(zone()); | 365 Schedule schedule(zone()); |
| 364 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size)); | 366 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, size)); |
| 365 base::SmartPointer<TestLoop> loop2(CreateLoop(&schedule, size)); | 367 std::unique_ptr<TestLoop> loop2(CreateLoop(&schedule, size)); |
| 366 BasicBlock* A = schedule.start(); | 368 BasicBlock* A = schedule.start(); |
| 367 BasicBlock* E = schedule.end(); | 369 BasicBlock* E = schedule.end(); |
| 368 | 370 |
| 369 schedule.AddSuccessorForTesting(A, loop1->header()); | 371 schedule.AddSuccessorForTesting(A, loop1->header()); |
| 370 schedule.AddSuccessorForTesting(loop1->nodes[exit], loop2->header()); | 372 schedule.AddSuccessorForTesting(loop1->nodes[exit], loop2->header()); |
| 371 schedule.AddSuccessorForTesting(loop2->nodes[exit], E); | 373 schedule.AddSuccessorForTesting(loop2->nodes[exit], E); |
| 372 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); | 374 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); |
| 373 | 375 |
| 374 EXPECT_EQ(schedule.BasicBlockCount(), order->size()); | 376 EXPECT_EQ(schedule.BasicBlockCount(), order->size()); |
| 375 CheckLoop(order, loop1->nodes, loop1->count); | 377 CheckLoop(order, loop1->nodes, loop1->count); |
| 376 CheckLoop(order, loop2->nodes, loop2->count); | 378 CheckLoop(order, loop2->nodes, loop2->count); |
| 377 } | 379 } |
| 378 } | 380 } |
| 379 } | 381 } |
| 380 | 382 |
| 381 TEST_F(SchedulerRPOTest, NestedLoopFollow1) { | 383 TEST_F(SchedulerRPOTest, NestedLoopFollow1) { |
| 382 Schedule schedule(zone()); | 384 Schedule schedule(zone()); |
| 383 | 385 |
| 384 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 1)); | 386 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, 1)); |
| 385 base::SmartPointer<TestLoop> loop2(CreateLoop(&schedule, 1)); | 387 std::unique_ptr<TestLoop> loop2(CreateLoop(&schedule, 1)); |
| 386 | 388 |
| 387 BasicBlock* A = schedule.start(); | 389 BasicBlock* A = schedule.start(); |
| 388 BasicBlock* B = schedule.NewBasicBlock(); | 390 BasicBlock* B = schedule.NewBasicBlock(); |
| 389 BasicBlock* C = schedule.NewBasicBlock(); | 391 BasicBlock* C = schedule.NewBasicBlock(); |
| 390 BasicBlock* E = schedule.end(); | 392 BasicBlock* E = schedule.end(); |
| 391 | 393 |
| 392 schedule.AddSuccessorForTesting(A, B); | 394 schedule.AddSuccessorForTesting(A, B); |
| 393 schedule.AddSuccessorForTesting(B, loop1->header()); | 395 schedule.AddSuccessorForTesting(B, loop1->header()); |
| 394 schedule.AddSuccessorForTesting(loop1->header(), loop2->header()); | 396 schedule.AddSuccessorForTesting(loop1->header(), loop2->header()); |
| 395 schedule.AddSuccessorForTesting(loop2->last(), C); | 397 schedule.AddSuccessorForTesting(loop2->last(), C); |
| (...skipping 11 matching lines...) Expand all Loading... |
| 407 } | 409 } |
| 408 | 410 |
| 409 TEST_F(SchedulerRPOTest, LoopBackedges1) { | 411 TEST_F(SchedulerRPOTest, LoopBackedges1) { |
| 410 int size = 8; | 412 int size = 8; |
| 411 for (int i = 0; i < size; i++) { | 413 for (int i = 0; i < size; i++) { |
| 412 for (int j = 0; j < size; j++) { | 414 for (int j = 0; j < size; j++) { |
| 413 Schedule schedule(zone()); | 415 Schedule schedule(zone()); |
| 414 BasicBlock* A = schedule.start(); | 416 BasicBlock* A = schedule.start(); |
| 415 BasicBlock* E = schedule.end(); | 417 BasicBlock* E = schedule.end(); |
| 416 | 418 |
| 417 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size)); | 419 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, size)); |
| 418 schedule.AddSuccessorForTesting(A, loop1->header()); | 420 schedule.AddSuccessorForTesting(A, loop1->header()); |
| 419 schedule.AddSuccessorForTesting(loop1->last(), E); | 421 schedule.AddSuccessorForTesting(loop1->last(), E); |
| 420 | 422 |
| 421 schedule.AddSuccessorForTesting(loop1->nodes[i], loop1->header()); | 423 schedule.AddSuccessorForTesting(loop1->nodes[i], loop1->header()); |
| 422 schedule.AddSuccessorForTesting(loop1->nodes[j], E); | 424 schedule.AddSuccessorForTesting(loop1->nodes[j], E); |
| 423 | 425 |
| 424 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); | 426 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); |
| 425 CheckRPONumbers(order, schedule.BasicBlockCount(), true); | 427 CheckRPONumbers(order, schedule.BasicBlockCount(), true); |
| 426 CheckLoop(order, loop1->nodes, loop1->count); | 428 CheckLoop(order, loop1->nodes, loop1->count); |
| 427 } | 429 } |
| 428 } | 430 } |
| 429 } | 431 } |
| 430 | 432 |
| 431 TEST_F(SchedulerRPOTest, LoopOutedges1) { | 433 TEST_F(SchedulerRPOTest, LoopOutedges1) { |
| 432 int size = 8; | 434 int size = 8; |
| 433 for (int i = 0; i < size; i++) { | 435 for (int i = 0; i < size; i++) { |
| 434 for (int j = 0; j < size; j++) { | 436 for (int j = 0; j < size; j++) { |
| 435 Schedule schedule(zone()); | 437 Schedule schedule(zone()); |
| 436 BasicBlock* A = schedule.start(); | 438 BasicBlock* A = schedule.start(); |
| 437 BasicBlock* D = schedule.NewBasicBlock(); | 439 BasicBlock* D = schedule.NewBasicBlock(); |
| 438 BasicBlock* E = schedule.end(); | 440 BasicBlock* E = schedule.end(); |
| 439 | 441 |
| 440 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size)); | 442 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, size)); |
| 441 schedule.AddSuccessorForTesting(A, loop1->header()); | 443 schedule.AddSuccessorForTesting(A, loop1->header()); |
| 442 schedule.AddSuccessorForTesting(loop1->last(), E); | 444 schedule.AddSuccessorForTesting(loop1->last(), E); |
| 443 | 445 |
| 444 schedule.AddSuccessorForTesting(loop1->nodes[i], loop1->header()); | 446 schedule.AddSuccessorForTesting(loop1->nodes[i], loop1->header()); |
| 445 schedule.AddSuccessorForTesting(loop1->nodes[j], D); | 447 schedule.AddSuccessorForTesting(loop1->nodes[j], D); |
| 446 schedule.AddSuccessorForTesting(D, E); | 448 schedule.AddSuccessorForTesting(D, E); |
| 447 | 449 |
| 448 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); | 450 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); |
| 449 CheckRPONumbers(order, schedule.BasicBlockCount(), true); | 451 CheckRPONumbers(order, schedule.BasicBlockCount(), true); |
| 450 CheckLoop(order, loop1->nodes, loop1->count); | 452 CheckLoop(order, loop1->nodes, loop1->count); |
| 451 } | 453 } |
| 452 } | 454 } |
| 453 } | 455 } |
| 454 | 456 |
| 455 TEST_F(SchedulerRPOTest, LoopOutedges2) { | 457 TEST_F(SchedulerRPOTest, LoopOutedges2) { |
| 456 int size = 8; | 458 int size = 8; |
| 457 for (int i = 0; i < size; i++) { | 459 for (int i = 0; i < size; i++) { |
| 458 Schedule schedule(zone()); | 460 Schedule schedule(zone()); |
| 459 BasicBlock* A = schedule.start(); | 461 BasicBlock* A = schedule.start(); |
| 460 BasicBlock* E = schedule.end(); | 462 BasicBlock* E = schedule.end(); |
| 461 | 463 |
| 462 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size)); | 464 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, size)); |
| 463 schedule.AddSuccessorForTesting(A, loop1->header()); | 465 schedule.AddSuccessorForTesting(A, loop1->header()); |
| 464 schedule.AddSuccessorForTesting(loop1->last(), E); | 466 schedule.AddSuccessorForTesting(loop1->last(), E); |
| 465 | 467 |
| 466 for (int j = 0; j < size; j++) { | 468 for (int j = 0; j < size; j++) { |
| 467 BasicBlock* O = schedule.NewBasicBlock(); | 469 BasicBlock* O = schedule.NewBasicBlock(); |
| 468 schedule.AddSuccessorForTesting(loop1->nodes[j], O); | 470 schedule.AddSuccessorForTesting(loop1->nodes[j], O); |
| 469 schedule.AddSuccessorForTesting(O, E); | 471 schedule.AddSuccessorForTesting(O, E); |
| 470 } | 472 } |
| 471 | 473 |
| 472 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); | 474 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); |
| 473 CheckRPONumbers(order, schedule.BasicBlockCount(), true); | 475 CheckRPONumbers(order, schedule.BasicBlockCount(), true); |
| 474 CheckLoop(order, loop1->nodes, loop1->count); | 476 CheckLoop(order, loop1->nodes, loop1->count); |
| 475 } | 477 } |
| 476 } | 478 } |
| 477 | 479 |
| 478 TEST_F(SchedulerRPOTest, LoopOutloops1) { | 480 TEST_F(SchedulerRPOTest, LoopOutloops1) { |
| 479 int size = 8; | 481 int size = 8; |
| 480 for (int i = 0; i < size; i++) { | 482 for (int i = 0; i < size; i++) { |
| 481 Schedule schedule(zone()); | 483 Schedule schedule(zone()); |
| 482 BasicBlock* A = schedule.start(); | 484 BasicBlock* A = schedule.start(); |
| 483 BasicBlock* E = schedule.end(); | 485 BasicBlock* E = schedule.end(); |
| 484 base::SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size)); | 486 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, size)); |
| 485 schedule.AddSuccessorForTesting(A, loop1->header()); | 487 schedule.AddSuccessorForTesting(A, loop1->header()); |
| 486 schedule.AddSuccessorForTesting(loop1->last(), E); | 488 schedule.AddSuccessorForTesting(loop1->last(), E); |
| 487 | 489 |
| 488 TestLoop** loopN = new TestLoop*[size]; | 490 TestLoop** loopN = new TestLoop*[size]; |
| 489 for (int j = 0; j < size; j++) { | 491 for (int j = 0; j < size; j++) { |
| 490 loopN[j] = CreateLoop(&schedule, 2); | 492 loopN[j] = CreateLoop(&schedule, 2); |
| 491 schedule.AddSuccessorForTesting(loop1->nodes[j], loopN[j]->header()); | 493 schedule.AddSuccessorForTesting(loop1->nodes[j], loopN[j]->header()); |
| 492 schedule.AddSuccessorForTesting(loopN[j]->last(), E); | 494 schedule.AddSuccessorForTesting(loopN[j]->last(), E); |
| 493 } | 495 } |
| 494 | 496 |
| (...skipping 29 matching lines...) Expand all Loading... |
| 524 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); | 526 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule); |
| 525 CheckRPONumbers(order, 5, true); | 527 CheckRPONumbers(order, 5, true); |
| 526 | 528 |
| 527 BasicBlock* loop1[] = {B, C, D, E}; | 529 BasicBlock* loop1[] = {B, C, D, E}; |
| 528 CheckLoop(order, loop1, 4); | 530 CheckLoop(order, loop1, 4); |
| 529 } | 531 } |
| 530 | 532 |
| 531 } // namespace compiler | 533 } // namespace compiler |
| 532 } // namespace internal | 534 } // namespace internal |
| 533 } // namespace v8 | 535 } // namespace v8 |
| OLD | NEW |