OLD | NEW |
1 // Copyright 2013 the V8 project authors. All rights reserved. | 1 // Copyright 2013 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 <deque> | 5 #include <deque> |
6 #include <queue> | 6 #include <queue> |
7 | 7 |
8 #include "src/compiler/scheduler.h" | 8 #include "src/compiler/scheduler.h" |
9 | 9 |
10 #include "src/compiler/graph.h" | 10 #include "src/compiler/graph.h" |
(...skipping 16 matching lines...) Expand all Loading... |
27 } | 27 } |
28 } | 28 } |
29 | 29 |
30 | 30 |
31 Scheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule) | 31 Scheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule) |
32 : zone_(zone), | 32 : zone_(zone), |
33 graph_(graph), | 33 graph_(graph), |
34 schedule_(schedule), | 34 schedule_(schedule), |
35 scheduled_nodes_(zone), | 35 scheduled_nodes_(zone), |
36 schedule_root_nodes_(zone), | 36 schedule_root_nodes_(zone), |
37 node_data_(graph_->NodeCount(), DefaultSchedulerData(zone), zone), | 37 node_data_(graph_->NodeCount(), DefaultSchedulerData(), zone), |
38 has_floating_control_(false) {} | 38 has_floating_control_(false) {} |
39 | 39 |
40 | 40 |
41 Schedule* Scheduler::ComputeSchedule(Graph* graph) { | 41 Schedule* Scheduler::ComputeSchedule(Graph* graph) { |
42 Schedule* schedule; | 42 Schedule* schedule; |
43 bool had_floating_control = false; | 43 bool had_floating_control = false; |
44 do { | 44 do { |
45 Zone tmp_zone(graph->zone()->isolate()); | 45 Zone tmp_zone(graph->zone()->isolate()); |
46 schedule = new (graph->zone()) | 46 schedule = new (graph->zone()) |
47 Schedule(graph->zone(), static_cast<size_t>(graph->NodeCount())); | 47 Schedule(graph->zone(), static_cast<size_t>(graph->NodeCount())); |
48 Scheduler scheduler(&tmp_zone, graph, schedule); | 48 Scheduler scheduler(&tmp_zone, graph, schedule); |
49 | 49 |
50 scheduler.BuildCFG(); | 50 scheduler.BuildCFG(); |
51 Scheduler::ComputeSpecialRPO(schedule); | 51 Scheduler::ComputeSpecialRPO(schedule); |
52 scheduler.GenerateImmediateDominatorTree(); | 52 scheduler.GenerateImmediateDominatorTree(); |
53 | 53 |
54 scheduler.PrepareUses(); | 54 scheduler.PrepareUses(); |
55 scheduler.ScheduleEarly(); | 55 scheduler.ScheduleEarly(); |
56 scheduler.ScheduleLate(); | 56 scheduler.ScheduleLate(); |
57 | 57 |
58 had_floating_control = scheduler.ConnectFloatingControl(); | 58 had_floating_control = scheduler.ConnectFloatingControl(); |
59 } while (had_floating_control); | 59 } while (had_floating_control); |
60 | 60 |
61 return schedule; | 61 return schedule; |
62 } | 62 } |
63 | 63 |
64 | 64 |
65 Scheduler::SchedulerData Scheduler::DefaultSchedulerData(Zone* zone) { | 65 Scheduler::SchedulerData Scheduler::DefaultSchedulerData() { |
66 SchedulerData def = {0, -1, false, false, kUnknown, NodeVector(zone)}; | 66 SchedulerData def = {0, -1, false, false, kUnknown}; |
67 return def; | 67 return def; |
68 } | 68 } |
69 | 69 |
70 | 70 |
71 Scheduler::Placement Scheduler::GetPlacement(Node* node) { | 71 Scheduler::Placement Scheduler::GetPlacement(Node* node) { |
72 SchedulerData* data = GetData(node); | 72 SchedulerData* data = GetData(node); |
73 if (data->placement_ == kUnknown) { // Compute placement, once, on demand. | 73 if (data->placement_ == kUnknown) { // Compute placement, once, on demand. |
74 switch (node->opcode()) { | 74 switch (node->opcode()) { |
75 case IrOpcode::kParameter: | 75 case IrOpcode::kParameter: |
76 // Parameters are always fixed to the start node. | 76 // Parameters are always fixed to the start node. |
(...skipping 98 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
175 // Mark the connected control nodes as they queued. | 175 // Mark the connected control nodes as they queued. |
176 Scheduler::SchedulerData* data = scheduler_->GetData(node); | 176 Scheduler::SchedulerData* data = scheduler_->GetData(node); |
177 if (!data->is_connected_control_) { | 177 if (!data->is_connected_control_) { |
178 BuildBlocks(node); | 178 BuildBlocks(node); |
179 queue_.push(node); | 179 queue_.push(node); |
180 control_.push_back(node); | 180 control_.push_back(node); |
181 data->is_connected_control_ = true; | 181 data->is_connected_control_ = true; |
182 } | 182 } |
183 } | 183 } |
184 | 184 |
185 | |
186 void BuildBlocks(Node* node) { | 185 void BuildBlocks(Node* node) { |
187 switch (node->opcode()) { | 186 switch (node->opcode()) { |
188 case IrOpcode::kLoop: | 187 case IrOpcode::kLoop: |
189 case IrOpcode::kMerge: | 188 case IrOpcode::kMerge: |
190 BuildBlockForNode(node); | 189 BuildBlockForNode(node); |
191 break; | 190 break; |
192 case IrOpcode::kBranch: | 191 case IrOpcode::kBranch: |
193 BuildBlocksForSuccessors(node, IrOpcode::kIfTrue, IrOpcode::kIfFalse); | 192 BuildBlocksForSuccessors(node, IrOpcode::kIfTrue, IrOpcode::kIfFalse); |
194 break; | 193 break; |
195 default: | 194 default: |
(...skipping 193 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
389 void PostEdge(Node* from, int index, Node* to) { | 388 void PostEdge(Node* from, int index, Node* to) { |
390 // If the edge is from an unscheduled node, then tally it in the use count | 389 // If the edge is from an unscheduled node, then tally it in the use count |
391 // for all of its inputs. The same criterion will be used in ScheduleLate | 390 // for all of its inputs. The same criterion will be used in ScheduleLate |
392 // for decrementing use counts. | 391 // for decrementing use counts. |
393 if (!schedule_->IsScheduled(from)) { | 392 if (!schedule_->IsScheduled(from)) { |
394 DCHECK_NE(Scheduler::kFixed, scheduler_->GetPlacement(from)); | 393 DCHECK_NE(Scheduler::kFixed, scheduler_->GetPlacement(from)); |
395 ++(scheduler_->GetData(to)->unscheduled_count_); | 394 ++(scheduler_->GetData(to)->unscheduled_count_); |
396 Trace(" Use count of #%d:%s (used by #%d:%s)++ = %d\n", to->id(), | 395 Trace(" Use count of #%d:%s (used by #%d:%s)++ = %d\n", to->id(), |
397 to->op()->mnemonic(), from->id(), from->op()->mnemonic(), | 396 to->op()->mnemonic(), from->id(), from->op()->mnemonic(), |
398 scheduler_->GetData(to)->unscheduled_count_); | 397 scheduler_->GetData(to)->unscheduled_count_); |
399 if (OperatorProperties::IsBasicBlockBegin(to->op()) && | |
400 (from->opcode() == IrOpcode::kEffectPhi || | |
401 from->opcode() == IrOpcode::kPhi) && | |
402 scheduler_->GetData(to)->is_floating_control_ && | |
403 !scheduler_->GetData(to)->is_connected_control_) { | |
404 for (InputIter i = from->inputs().begin(); i != from->inputs().end(); | |
405 ++i) { | |
406 if (!NodeProperties::IsControlEdge(i.edge())) { | |
407 Scheduler::SchedulerData* data = scheduler_->GetData(to); | |
408 data->additional_dependencies.push_back(*i); | |
409 ++(scheduler_->GetData(*i)->unscheduled_count_); | |
410 Trace( | |
411 " Use count of #%d:%s (additional dependency of #%d:%s)++ = " | |
412 "%d\n", | |
413 (*i)->id(), (*i)->op()->mnemonic(), to->id(), | |
414 to->op()->mnemonic(), | |
415 scheduler_->GetData(*i)->unscheduled_count_); | |
416 } | |
417 } | |
418 } | |
419 } | 398 } |
420 } | 399 } |
421 | 400 |
422 private: | 401 private: |
423 Scheduler* scheduler_; | 402 Scheduler* scheduler_; |
424 Schedule* schedule_; | 403 Schedule* schedule_; |
425 }; | 404 }; |
426 | 405 |
427 | 406 |
428 void Scheduler::PrepareUses() { | 407 void Scheduler::PrepareUses() { |
(...skipping 94 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
523 class ScheduleLateNodeVisitor : public NullNodeVisitor { | 502 class ScheduleLateNodeVisitor : public NullNodeVisitor { |
524 public: | 503 public: |
525 explicit ScheduleLateNodeVisitor(Scheduler* scheduler) | 504 explicit ScheduleLateNodeVisitor(Scheduler* scheduler) |
526 : scheduler_(scheduler), schedule_(scheduler_->schedule_) {} | 505 : scheduler_(scheduler), schedule_(scheduler_->schedule_) {} |
527 | 506 |
528 GenericGraphVisit::Control Pre(Node* node) { | 507 GenericGraphVisit::Control Pre(Node* node) { |
529 // Don't schedule nodes that are already scheduled. | 508 // Don't schedule nodes that are already scheduled. |
530 if (schedule_->IsScheduled(node)) { | 509 if (schedule_->IsScheduled(node)) { |
531 return GenericGraphVisit::CONTINUE; | 510 return GenericGraphVisit::CONTINUE; |
532 } | 511 } |
533 | |
534 Scheduler::SchedulerData* data = scheduler_->GetData(node); | 512 Scheduler::SchedulerData* data = scheduler_->GetData(node); |
535 DCHECK_EQ(Scheduler::kSchedulable, data->placement_); | 513 DCHECK_EQ(Scheduler::kSchedulable, data->placement_); |
536 | 514 |
537 // If all the uses of a node have been scheduled, then the node itself can | 515 // If all the uses of a node have been scheduled, then the node itself can |
538 // be scheduled. | 516 // be scheduled. |
539 bool eligible = data->unscheduled_count_ == 0; | 517 bool eligible = data->unscheduled_count_ == 0; |
540 Trace("Testing for schedule eligibility for #%d:%s = %s\n", node->id(), | 518 Trace("Testing for schedule eligibility for #%d:%s = %s\n", node->id(), |
541 node->op()->mnemonic(), eligible ? "true" : "false"); | 519 node->op()->mnemonic(), eligible ? "true" : "false"); |
542 if (!eligible) return GenericGraphVisit::DEFER; | 520 if (!eligible) return GenericGraphVisit::DEFER; |
543 | 521 |
(...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
626 if (FLAG_trace_turbo_scheduler) { | 604 if (FLAG_trace_turbo_scheduler) { |
627 Trace(" Use count for #%d:%s (used by #%d:%s)-- = %d\n", (*i)->id(), | 605 Trace(" Use count for #%d:%s (used by #%d:%s)-- = %d\n", (*i)->id(), |
628 (*i)->op()->mnemonic(), i.edge().from()->id(), | 606 (*i)->op()->mnemonic(), i.edge().from()->id(), |
629 i.edge().from()->op()->mnemonic(), data->unscheduled_count_); | 607 i.edge().from()->op()->mnemonic(), data->unscheduled_count_); |
630 if (data->unscheduled_count_ == 0) { | 608 if (data->unscheduled_count_ == 0) { |
631 Trace(" newly eligible #%d:%s\n", (*i)->id(), | 609 Trace(" newly eligible #%d:%s\n", (*i)->id(), |
632 (*i)->op()->mnemonic()); | 610 (*i)->op()->mnemonic()); |
633 } | 611 } |
634 } | 612 } |
635 } | 613 } |
636 | |
637 Scheduler::SchedulerData* data = scheduler_->GetData(node); | |
638 for (NodeVectorIter i = data->additional_dependencies.begin(); | |
639 i != data->additional_dependencies.end(); ++i) { | |
640 Scheduler::SchedulerData* data = scheduler_->GetData(*i); | |
641 DCHECK(data->unscheduled_count_ > 0); | |
642 --data->unscheduled_count_; | |
643 if (FLAG_trace_turbo_scheduler) { | |
644 Trace( | |
645 " Use count for #%d:%s (additional dependency of #%d:%s)-- = %d\n", | |
646 (*i)->id(), (*i)->op()->mnemonic(), node->id(), | |
647 node->op()->mnemonic(), data->unscheduled_count_); | |
648 if (data->unscheduled_count_ == 0) { | |
649 Trace(" newly eligible #%d:%s\n", (*i)->id(), | |
650 (*i)->op()->mnemonic()); | |
651 } | |
652 } | |
653 } | |
654 } | 614 } |
655 | 615 |
656 Scheduler* scheduler_; | 616 Scheduler* scheduler_; |
657 Schedule* schedule_; | 617 Schedule* schedule_; |
658 }; | 618 }; |
659 | 619 |
660 | 620 |
661 void Scheduler::ScheduleLate() { | 621 void Scheduler::ScheduleLate() { |
662 Trace("------------------- SCHEDULE LATE -----------------\n"); | 622 Trace("------------------- SCHEDULE LATE -----------------\n"); |
663 if (FLAG_trace_turbo_scheduler) { | 623 if (FLAG_trace_turbo_scheduler) { |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
702 | 662 |
703 // Process blocks and instructions backwards to find and connect floating | 663 // Process blocks and instructions backwards to find and connect floating |
704 // control nodes into the control graph according to the block they were | 664 // control nodes into the control graph according to the block they were |
705 // scheduled into. | 665 // scheduled into. |
706 int max = static_cast<int>(schedule_->rpo_order()->size()); | 666 int max = static_cast<int>(schedule_->rpo_order()->size()); |
707 for (int i = max - 1; i >= 0; i--) { | 667 for (int i = max - 1; i >= 0; i--) { |
708 BasicBlock* block = schedule_->rpo_order()->at(i); | 668 BasicBlock* block = schedule_->rpo_order()->at(i); |
709 // TODO(titzer): we place at most one floating control structure per | 669 // TODO(titzer): we place at most one floating control structure per |
710 // basic block because scheduling currently can interleave phis from | 670 // basic block because scheduling currently can interleave phis from |
711 // one subgraph with the merges from another subgraph. | 671 // one subgraph with the merges from another subgraph. |
| 672 bool one_placed = false; |
712 for (size_t j = 0; j < block->NodeCount(); j++) { | 673 for (size_t j = 0; j < block->NodeCount(); j++) { |
713 Node* node = block->NodeAt(block->NodeCount() - 1 - j); | 674 Node* node = block->NodeAt(block->NodeCount() - 1 - j); |
714 SchedulerData* data = GetData(node); | 675 SchedulerData* data = GetData(node); |
715 if (data->is_floating_control_ && !data->is_connected_control_) { | 676 if (data->is_floating_control_ && !data->is_connected_control_ && |
| 677 !one_placed) { |
716 Trace(" Floating control #%d:%s was scheduled in B%d\n", node->id(), | 678 Trace(" Floating control #%d:%s was scheduled in B%d\n", node->id(), |
717 node->op()->mnemonic(), block->id().ToInt()); | 679 node->op()->mnemonic(), block->id().ToInt()); |
718 ConnectFloatingControlSubgraph(block, node); | 680 ConnectFloatingControlSubgraph(block, node); |
719 return true; | 681 one_placed = true; |
720 } | 682 } |
721 } | 683 } |
722 } | 684 } |
723 | 685 |
724 return true; | 686 return true; |
725 } | 687 } |
726 | 688 |
727 | 689 |
728 void Scheduler::ConnectFloatingControlSubgraph(BasicBlock* block, Node* end) { | 690 void Scheduler::ConnectFloatingControlSubgraph(BasicBlock* block, Node* end) { |
729 Node* block_start = block->NodeAt(0); | 691 Node* block_start = block->NodeAt(0); |
(...skipping 460 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1190 #if DEBUG | 1152 #if DEBUG |
1191 if (FLAG_trace_turbo_scheduler) PrintRPO(num_loops, loops, final_order); | 1153 if (FLAG_trace_turbo_scheduler) PrintRPO(num_loops, loops, final_order); |
1192 VerifySpecialRPO(num_loops, loops, final_order); | 1154 VerifySpecialRPO(num_loops, loops, final_order); |
1193 #endif | 1155 #endif |
1194 return final_order; | 1156 return final_order; |
1195 } | 1157 } |
1196 | 1158 |
1197 } // namespace compiler | 1159 } // namespace compiler |
1198 } // namespace internal | 1160 } // namespace internal |
1199 } // namespace v8 | 1161 } // namespace v8 |
OLD | NEW |