OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 1 // Copyright 2014 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 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 "src/v8.h" | 5 #include "src/v8.h" |
6 #include "test/cctest/cctest.h" | 6 #include "test/cctest/cctest.h" |
7 | 7 |
8 #include "src/compiler/common-operator.h" | 8 #include "src/compiler/common-operator.h" |
9 #include "src/compiler/generic-node-inl.h" | 9 #include "src/compiler/generic-node-inl.h" |
10 #include "src/compiler/generic-node.h" | 10 #include "src/compiler/generic-node.h" |
(...skipping 26 matching lines...) Expand all Loading... |
37 loop->nodes = new BasicBlock* [count]; | 37 loop->nodes = new BasicBlock* [count]; |
38 for (int i = 0; i < count; i++) { | 38 for (int i = 0; i < count; i++) { |
39 loop->nodes[i] = schedule->NewBasicBlock(); | 39 loop->nodes[i] = schedule->NewBasicBlock(); |
40 if (i > 0) schedule->AddSuccessor(loop->nodes[i - 1], loop->nodes[i]); | 40 if (i > 0) schedule->AddSuccessor(loop->nodes[i - 1], loop->nodes[i]); |
41 } | 41 } |
42 schedule->AddSuccessor(loop->nodes[count - 1], loop->nodes[0]); | 42 schedule->AddSuccessor(loop->nodes[count - 1], loop->nodes[0]); |
43 return loop; | 43 return loop; |
44 } | 44 } |
45 | 45 |
46 | 46 |
47 static void CheckRPONumbers(BasicBlockVector* order, int expected, | 47 static void CheckRPONumbers(BasicBlockVector* order, size_t expected, |
48 bool loops_allowed) { | 48 bool loops_allowed) { |
49 CHECK_EQ(expected, static_cast<int>(order->size())); | 49 CHECK(expected == order->size()); |
50 for (int i = 0; i < static_cast<int>(order->size()); i++) { | 50 for (int i = 0; i < static_cast<int>(order->size()); i++) { |
51 CHECK(order->at(i)->rpo_number_ == i); | 51 CHECK(order->at(i)->rpo_number() == i); |
52 if (!loops_allowed) CHECK_LT(order->at(i)->loop_end_, 0); | 52 if (!loops_allowed) CHECK_LT(order->at(i)->loop_end(), 0); |
53 } | 53 } |
54 } | 54 } |
55 | 55 |
56 | 56 |
57 static void CheckLoopContains(BasicBlock** blocks, int body_size) { | 57 static void CheckLoopContains(BasicBlock** blocks, int body_size) { |
58 BasicBlock* header = blocks[0]; | 58 BasicBlock* header = blocks[0]; |
59 CHECK_GT(header->loop_end_, 0); | 59 CHECK_GT(header->loop_end(), 0); |
60 CHECK_EQ(body_size, (header->loop_end_ - header->rpo_number_)); | 60 CHECK_EQ(body_size, (header->loop_end() - header->rpo_number())); |
61 for (int i = 0; i < body_size; i++) { | 61 for (int i = 0; i < body_size; i++) { |
62 int num = blocks[i]->rpo_number_; | 62 int num = blocks[i]->rpo_number(); |
63 CHECK(num >= header->rpo_number_ && num < header->loop_end_); | 63 CHECK(num >= header->rpo_number() && num < header->loop_end()); |
64 CHECK(header->LoopContains(blocks[i])); | 64 CHECK(header->LoopContains(blocks[i])); |
65 CHECK(header->IsLoopHeader() || blocks[i]->loop_header_ == header); | 65 CHECK(header->IsLoopHeader() || blocks[i]->loop_header() == header); |
66 } | 66 } |
67 } | 67 } |
68 | 68 |
69 | 69 |
70 static int GetScheduledNodeCount(Schedule* schedule) { | 70 static int GetScheduledNodeCount(Schedule* schedule) { |
71 int node_count = 0; | 71 int node_count = 0; |
72 for (BasicBlockVectorIter i = schedule->rpo_order()->begin(); | 72 for (BasicBlockVectorIter i = schedule->rpo_order()->begin(); |
73 i != schedule->rpo_order()->end(); ++i) { | 73 i != schedule->rpo_order()->end(); ++i) { |
74 BasicBlock* block = *i; | 74 BasicBlock* block = *i; |
75 for (BasicBlock::const_iterator j = block->begin(); j != block->end(); | 75 for (BasicBlock::const_iterator j = block->begin(); j != block->end(); |
76 ++j) { | 76 ++j) { |
77 ++node_count; | 77 ++node_count; |
78 } | 78 } |
79 BasicBlock::Control control = block->control_; | 79 BasicBlock::Control control = block->control(); |
80 if (control != BasicBlock::kNone) { | 80 if (control != BasicBlock::kNone) { |
81 ++node_count; | 81 ++node_count; |
82 } | 82 } |
83 } | 83 } |
84 return node_count; | 84 return node_count; |
85 } | 85 } |
86 | 86 |
87 | 87 |
88 static Schedule* ComputeAndVerifySchedule(int expected, Graph* graph) { | 88 static Schedule* ComputeAndVerifySchedule(int expected, Graph* graph) { |
89 if (FLAG_trace_turbo) { | 89 if (FLAG_trace_turbo) { |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
133 | 133 |
134 BasicBlock* last = schedule.start(); | 134 BasicBlock* last = schedule.start(); |
135 for (int j = 0; j < i; j++) { | 135 for (int j = 0; j < i; j++) { |
136 BasicBlock* block = schedule.NewBasicBlock(); | 136 BasicBlock* block = schedule.NewBasicBlock(); |
137 schedule.AddGoto(last, block); | 137 schedule.AddGoto(last, block); |
138 last = block; | 138 last = block; |
139 } | 139 } |
140 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule); | 140 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule); |
141 CheckRPONumbers(order, 1 + i, false); | 141 CheckRPONumbers(order, 1 + i, false); |
142 | 142 |
143 Schedule::BasicBlocks blocks(schedule.all_blocks()); | 143 for (size_t i = 0; i < schedule.BasicBlockCount(); i++) { |
144 for (Schedule::BasicBlocks::iterator iter = blocks.begin(); | 144 BasicBlock* block = schedule.GetBlockById(BasicBlock::Id::FromSize(i)); |
145 iter != blocks.end(); ++iter) { | 145 if (block->rpo_number() >= 0 && block->SuccessorCount() == 1) { |
146 BasicBlock* block = *iter; | 146 CHECK(block->rpo_number() + 1 == block->SuccessorAt(0)->rpo_number()); |
147 if (block->rpo_number_ >= 0 && block->SuccessorCount() == 1) { | |
148 CHECK(block->rpo_number_ + 1 == block->SuccessorAt(0)->rpo_number_); | |
149 } | 147 } |
150 } | 148 } |
151 } | 149 } |
152 } | 150 } |
153 | 151 |
154 | 152 |
155 TEST(RPOSelfLoop) { | 153 TEST(RPOSelfLoop) { |
156 HandleAndZoneScope scope; | 154 HandleAndZoneScope scope; |
157 Schedule schedule(scope.main_zone()); | 155 Schedule schedule(scope.main_zone()); |
158 schedule.AddSuccessor(schedule.start(), schedule.start()); | 156 schedule.AddSuccessor(schedule.start(), schedule.start()); |
(...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
208 BasicBlock* D = schedule.end(); | 206 BasicBlock* D = schedule.end(); |
209 | 207 |
210 schedule.AddSuccessor(A, B); | 208 schedule.AddSuccessor(A, B); |
211 schedule.AddSuccessor(A, C); | 209 schedule.AddSuccessor(A, C); |
212 schedule.AddSuccessor(B, D); | 210 schedule.AddSuccessor(B, D); |
213 schedule.AddSuccessor(C, D); | 211 schedule.AddSuccessor(C, D); |
214 | 212 |
215 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule); | 213 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule); |
216 CheckRPONumbers(order, 4, false); | 214 CheckRPONumbers(order, 4, false); |
217 | 215 |
218 CHECK_EQ(0, A->rpo_number_); | 216 CHECK_EQ(0, A->rpo_number()); |
219 CHECK((B->rpo_number_ == 1 && C->rpo_number_ == 2) || | 217 CHECK((B->rpo_number() == 1 && C->rpo_number() == 2) || |
220 (B->rpo_number_ == 2 && C->rpo_number_ == 1)); | 218 (B->rpo_number() == 2 && C->rpo_number() == 1)); |
221 CHECK_EQ(3, D->rpo_number_); | 219 CHECK_EQ(3, D->rpo_number()); |
222 } | 220 } |
223 | 221 |
224 | 222 |
225 TEST(RPOLoop1) { | 223 TEST(RPOLoop1) { |
226 HandleAndZoneScope scope; | 224 HandleAndZoneScope scope; |
227 Schedule schedule(scope.main_zone()); | 225 Schedule schedule(scope.main_zone()); |
228 | 226 |
229 BasicBlock* A = schedule.start(); | 227 BasicBlock* A = schedule.start(); |
230 BasicBlock* B = schedule.NewBasicBlock(); | 228 BasicBlock* B = schedule.NewBasicBlock(); |
231 BasicBlock* C = schedule.NewBasicBlock(); | 229 BasicBlock* C = schedule.NewBasicBlock(); |
(...skipping 153 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
385 BasicBlock* E = schedule.end(); | 383 BasicBlock* E = schedule.end(); |
386 | 384 |
387 schedule.AddSuccessor(A, loop1->header()); | 385 schedule.AddSuccessor(A, loop1->header()); |
388 schedule.AddSuccessor(loop1->header(), loop2->header()); | 386 schedule.AddSuccessor(loop1->header(), loop2->header()); |
389 schedule.AddSuccessor(loop2->last(), E); | 387 schedule.AddSuccessor(loop2->last(), E); |
390 | 388 |
391 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule); | 389 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule); |
392 | 390 |
393 CheckLoopContains(loop1->nodes, loop1->count); | 391 CheckLoopContains(loop1->nodes, loop1->count); |
394 | 392 |
395 CHECK_EQ(schedule.BasicBlockCount(), static_cast<int>(order->size())); | 393 CHECK_EQ(static_cast<int>(schedule.BasicBlockCount()), |
| 394 static_cast<int>(order->size())); |
396 CheckLoopContains(loop1->nodes, loop1->count); | 395 CheckLoopContains(loop1->nodes, loop1->count); |
397 CheckLoopContains(loop2->nodes, loop2->count); | 396 CheckLoopContains(loop2->nodes, loop2->count); |
398 } | 397 } |
399 | 398 |
400 | 399 |
401 TEST(RPOLoopFollow2) { | 400 TEST(RPOLoopFollow2) { |
402 HandleAndZoneScope scope; | 401 HandleAndZoneScope scope; |
403 Schedule schedule(scope.main_zone()); | 402 Schedule schedule(scope.main_zone()); |
404 | 403 |
405 SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 1)); | 404 SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 1)); |
406 SmartPointer<TestLoop> loop2(CreateLoop(&schedule, 1)); | 405 SmartPointer<TestLoop> loop2(CreateLoop(&schedule, 1)); |
407 | 406 |
408 BasicBlock* A = schedule.start(); | 407 BasicBlock* A = schedule.start(); |
409 BasicBlock* S = schedule.NewBasicBlock(); | 408 BasicBlock* S = schedule.NewBasicBlock(); |
410 BasicBlock* E = schedule.end(); | 409 BasicBlock* E = schedule.end(); |
411 | 410 |
412 schedule.AddSuccessor(A, loop1->header()); | 411 schedule.AddSuccessor(A, loop1->header()); |
413 schedule.AddSuccessor(loop1->header(), S); | 412 schedule.AddSuccessor(loop1->header(), S); |
414 schedule.AddSuccessor(S, loop2->header()); | 413 schedule.AddSuccessor(S, loop2->header()); |
415 schedule.AddSuccessor(loop2->last(), E); | 414 schedule.AddSuccessor(loop2->last(), E); |
416 | 415 |
417 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule); | 416 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule); |
418 | 417 |
419 CheckLoopContains(loop1->nodes, loop1->count); | 418 CheckLoopContains(loop1->nodes, loop1->count); |
420 | 419 |
421 CHECK_EQ(schedule.BasicBlockCount(), static_cast<int>(order->size())); | 420 CHECK_EQ(static_cast<int>(schedule.BasicBlockCount()), |
| 421 static_cast<int>(order->size())); |
422 CheckLoopContains(loop1->nodes, loop1->count); | 422 CheckLoopContains(loop1->nodes, loop1->count); |
423 CheckLoopContains(loop2->nodes, loop2->count); | 423 CheckLoopContains(loop2->nodes, loop2->count); |
424 } | 424 } |
425 | 425 |
426 | 426 |
427 TEST(RPOLoopFollowN) { | 427 TEST(RPOLoopFollowN) { |
428 HandleAndZoneScope scope; | 428 HandleAndZoneScope scope; |
429 | 429 |
430 for (int size = 1; size < 5; size++) { | 430 for (int size = 1; size < 5; size++) { |
431 for (int exit = 0; exit < size; exit++) { | 431 for (int exit = 0; exit < size; exit++) { |
432 Schedule schedule(scope.main_zone()); | 432 Schedule schedule(scope.main_zone()); |
433 SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size)); | 433 SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size)); |
434 SmartPointer<TestLoop> loop2(CreateLoop(&schedule, size)); | 434 SmartPointer<TestLoop> loop2(CreateLoop(&schedule, size)); |
435 BasicBlock* A = schedule.start(); | 435 BasicBlock* A = schedule.start(); |
436 BasicBlock* E = schedule.end(); | 436 BasicBlock* E = schedule.end(); |
437 | 437 |
438 schedule.AddSuccessor(A, loop1->header()); | 438 schedule.AddSuccessor(A, loop1->header()); |
439 schedule.AddSuccessor(loop1->nodes[exit], loop2->header()); | 439 schedule.AddSuccessor(loop1->nodes[exit], loop2->header()); |
440 schedule.AddSuccessor(loop2->nodes[exit], E); | 440 schedule.AddSuccessor(loop2->nodes[exit], E); |
441 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule); | 441 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule); |
442 CheckLoopContains(loop1->nodes, loop1->count); | 442 CheckLoopContains(loop1->nodes, loop1->count); |
443 | 443 |
444 CHECK_EQ(schedule.BasicBlockCount(), static_cast<int>(order->size())); | 444 CHECK_EQ(static_cast<int>(schedule.BasicBlockCount()), |
| 445 static_cast<int>(order->size())); |
445 CheckLoopContains(loop1->nodes, loop1->count); | 446 CheckLoopContains(loop1->nodes, loop1->count); |
446 CheckLoopContains(loop2->nodes, loop2->count); | 447 CheckLoopContains(loop2->nodes, loop2->count); |
447 } | 448 } |
448 } | 449 } |
449 } | 450 } |
450 | 451 |
451 | 452 |
452 TEST(RPONestedLoopFollow1) { | 453 TEST(RPONestedLoopFollow1) { |
453 HandleAndZoneScope scope; | 454 HandleAndZoneScope scope; |
454 Schedule schedule(scope.main_zone()); | 455 Schedule schedule(scope.main_zone()); |
(...skipping 10 matching lines...) Expand all Loading... |
465 schedule.AddSuccessor(B, loop1->header()); | 466 schedule.AddSuccessor(B, loop1->header()); |
466 schedule.AddSuccessor(loop1->header(), loop2->header()); | 467 schedule.AddSuccessor(loop1->header(), loop2->header()); |
467 schedule.AddSuccessor(loop2->last(), C); | 468 schedule.AddSuccessor(loop2->last(), C); |
468 schedule.AddSuccessor(C, E); | 469 schedule.AddSuccessor(C, E); |
469 schedule.AddSuccessor(C, B); | 470 schedule.AddSuccessor(C, B); |
470 | 471 |
471 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule); | 472 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule); |
472 | 473 |
473 CheckLoopContains(loop1->nodes, loop1->count); | 474 CheckLoopContains(loop1->nodes, loop1->count); |
474 | 475 |
475 CHECK_EQ(schedule.BasicBlockCount(), static_cast<int>(order->size())); | 476 CHECK_EQ(static_cast<int>(schedule.BasicBlockCount()), |
| 477 static_cast<int>(order->size())); |
476 CheckLoopContains(loop1->nodes, loop1->count); | 478 CheckLoopContains(loop1->nodes, loop1->count); |
477 CheckLoopContains(loop2->nodes, loop2->count); | 479 CheckLoopContains(loop2->nodes, loop2->count); |
478 | 480 |
479 BasicBlock* loop3[] = {B, loop1->nodes[0], loop2->nodes[0], C}; | 481 BasicBlock* loop3[] = {B, loop1->nodes[0], loop2->nodes[0], C}; |
480 CheckLoopContains(loop3, 4); | 482 CheckLoopContains(loop3, 4); |
481 } | 483 } |
482 | 484 |
483 | 485 |
484 TEST(RPOLoopBackedges1) { | 486 TEST(RPOLoopBackedges1) { |
485 HandleAndZoneScope scope; | 487 HandleAndZoneScope scope; |
(...skipping 1218 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1704 Node* d3 = CreateDiamond(&graph, &common, add); | 1706 Node* d3 = CreateDiamond(&graph, &common, add); |
1705 Node* ret = graph.NewNode(common.Return(), d3, start, start); | 1707 Node* ret = graph.NewNode(common.Return(), d3, start, start); |
1706 Node* end = graph.NewNode(common.End(), ret, start); | 1708 Node* end = graph.NewNode(common.End(), ret, start); |
1707 | 1709 |
1708 graph.SetEnd(end); | 1710 graph.SetEnd(end); |
1709 | 1711 |
1710 ComputeAndVerifySchedule(33, &graph); | 1712 ComputeAndVerifySchedule(33, &graph); |
1711 } | 1713 } |
1712 | 1714 |
1713 #endif | 1715 #endif |
OLD | NEW |