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/bit-vector.h" | 10 #include "src/bit-vector.h" |
(...skipping 109 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
120 Node* control = NodeProperties::GetControlInput(node); | 120 Node* control = NodeProperties::GetControlInput(node); |
121 BasicBlock* block = schedule_->block(control); | 121 BasicBlock* block = schedule_->block(control); |
122 schedule_->AddNode(block, node); | 122 schedule_->AddNode(block, node); |
123 break; | 123 break; |
124 } | 124 } |
125 #define DEFINE_CONTROL_CASE(V) case IrOpcode::k##V: | 125 #define DEFINE_CONTROL_CASE(V) case IrOpcode::k##V: |
126 CONTROL_OP_LIST(DEFINE_CONTROL_CASE) | 126 CONTROL_OP_LIST(DEFINE_CONTROL_CASE) |
127 #undef DEFINE_CONTROL_CASE | 127 #undef DEFINE_CONTROL_CASE |
128 { | 128 { |
129 // Control nodes force coupled uses to be placed. | 129 // Control nodes force coupled uses to be placed. |
130 Node::Uses uses = node->uses(); | 130 for (auto use : node->uses()) { |
131 for (Node::Uses::iterator i = uses.begin(); i != uses.end(); ++i) { | 131 if (GetPlacement(use) == Scheduler::kCoupled) { |
132 if (GetPlacement(*i) == Scheduler::kCoupled) { | 132 DCHECK_EQ(node, NodeProperties::GetControlInput(use)); |
133 DCHECK_EQ(node, NodeProperties::GetControlInput(*i)); | 133 UpdatePlacement(use, placement); |
134 UpdatePlacement(*i, placement); | |
135 } | 134 } |
136 } | 135 } |
137 break; | 136 break; |
138 } | 137 } |
139 default: | 138 default: |
140 DCHECK_EQ(Scheduler::kSchedulable, data->placement_); | 139 DCHECK_EQ(Scheduler::kSchedulable, data->placement_); |
141 DCHECK_EQ(Scheduler::kScheduled, placement); | 140 DCHECK_EQ(Scheduler::kScheduled, placement); |
142 break; | 141 break; |
143 } | 142 } |
144 // Reduce the use count of the node's inputs to potentially make them | 143 // Reduce the use count of the node's inputs to potentially make them |
(...skipping 979 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1124 // Phase 4: Schedule nodes early. | 1123 // Phase 4: Schedule nodes early. |
1125 | 1124 |
1126 | 1125 |
1127 class ScheduleEarlyNodeVisitor { | 1126 class ScheduleEarlyNodeVisitor { |
1128 public: | 1127 public: |
1129 ScheduleEarlyNodeVisitor(Zone* zone, Scheduler* scheduler) | 1128 ScheduleEarlyNodeVisitor(Zone* zone, Scheduler* scheduler) |
1130 : scheduler_(scheduler), schedule_(scheduler->schedule_), queue_(zone) {} | 1129 : scheduler_(scheduler), schedule_(scheduler->schedule_), queue_(zone) {} |
1131 | 1130 |
1132 // Run the schedule early algorithm on a set of fixed root nodes. | 1131 // Run the schedule early algorithm on a set of fixed root nodes. |
1133 void Run(NodeVector* roots) { | 1132 void Run(NodeVector* roots) { |
1134 for (NodeVectorIter i = roots->begin(); i != roots->end(); ++i) { | 1133 for (Node* const root : *roots) { |
1135 queue_.push(*i); | 1134 queue_.push(root); |
1136 while (!queue_.empty()) { | 1135 while (!queue_.empty()) { |
1137 VisitNode(queue_.front()); | 1136 VisitNode(queue_.front()); |
1138 queue_.pop(); | 1137 queue_.pop(); |
1139 } | 1138 } |
1140 } | 1139 } |
1141 } | 1140 } |
1142 | 1141 |
1143 private: | 1142 private: |
1144 // Visits one node from the queue and propagates its current schedule early | 1143 // Visits one node from the queue and propagates its current schedule early |
1145 // position to all uses. This in turn might push more nodes onto the queue. | 1144 // position to all uses. This in turn might push more nodes onto the queue. |
1146 void VisitNode(Node* node) { | 1145 void VisitNode(Node* node) { |
1147 Scheduler::SchedulerData* data = scheduler_->GetData(node); | 1146 Scheduler::SchedulerData* data = scheduler_->GetData(node); |
1148 | 1147 |
1149 // Fixed nodes already know their schedule early position. | 1148 // Fixed nodes already know their schedule early position. |
1150 if (scheduler_->GetPlacement(node) == Scheduler::kFixed) { | 1149 if (scheduler_->GetPlacement(node) == Scheduler::kFixed) { |
1151 data->minimum_block_ = schedule_->block(node); | 1150 data->minimum_block_ = schedule_->block(node); |
1152 Trace("Fixing #%d:%s minimum_block = B%d, dominator_depth = %d\n", | 1151 Trace("Fixing #%d:%s minimum_block = B%d, dominator_depth = %d\n", |
1153 node->id(), node->op()->mnemonic(), | 1152 node->id(), node->op()->mnemonic(), |
1154 data->minimum_block_->id().ToInt(), | 1153 data->minimum_block_->id().ToInt(), |
1155 data->minimum_block_->dominator_depth()); | 1154 data->minimum_block_->dominator_depth()); |
1156 } | 1155 } |
1157 | 1156 |
1158 // No need to propagate unconstrained schedule early positions. | 1157 // No need to propagate unconstrained schedule early positions. |
1159 if (data->minimum_block_ == schedule_->start()) return; | 1158 if (data->minimum_block_ == schedule_->start()) return; |
1160 | 1159 |
1161 // Propagate schedule early position. | 1160 // Propagate schedule early position. |
1162 DCHECK(data->minimum_block_ != NULL); | 1161 DCHECK(data->minimum_block_ != NULL); |
1163 Node::Uses uses = node->uses(); | 1162 for (auto use : node->uses()) { |
1164 for (Node::Uses::iterator i = uses.begin(); i != uses.end(); ++i) { | 1163 PropagateMinimumPositionToNode(data->minimum_block_, use); |
1165 PropagateMinimumPositionToNode(data->minimum_block_, *i); | |
1166 } | 1164 } |
1167 } | 1165 } |
1168 | 1166 |
1169 // Propagates {block} as another minimum position into the given {node}. This | 1167 // Propagates {block} as another minimum position into the given {node}. This |
1170 // has the net effect of computing the minimum dominator block of {node} that | 1168 // has the net effect of computing the minimum dominator block of {node} that |
1171 // still post-dominates all inputs to {node} when the queue is processed. | 1169 // still post-dominates all inputs to {node} when the queue is processed. |
1172 void PropagateMinimumPositionToNode(BasicBlock* block, Node* node) { | 1170 void PropagateMinimumPositionToNode(BasicBlock* block, Node* node) { |
1173 Scheduler::SchedulerData* data = scheduler_->GetData(node); | 1171 Scheduler::SchedulerData* data = scheduler_->GetData(node); |
1174 | 1172 |
1175 // No need to propagate to fixed node, it's guaranteed to be a root. | 1173 // No need to propagate to fixed node, it's guaranteed to be a root. |
(...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1229 // Phase 5: Schedule nodes late. | 1227 // Phase 5: Schedule nodes late. |
1230 | 1228 |
1231 | 1229 |
1232 class ScheduleLateNodeVisitor { | 1230 class ScheduleLateNodeVisitor { |
1233 public: | 1231 public: |
1234 ScheduleLateNodeVisitor(Zone* zone, Scheduler* scheduler) | 1232 ScheduleLateNodeVisitor(Zone* zone, Scheduler* scheduler) |
1235 : scheduler_(scheduler), schedule_(scheduler_->schedule_) {} | 1233 : scheduler_(scheduler), schedule_(scheduler_->schedule_) {} |
1236 | 1234 |
1237 // Run the schedule late algorithm on a set of fixed root nodes. | 1235 // Run the schedule late algorithm on a set of fixed root nodes. |
1238 void Run(NodeVector* roots) { | 1236 void Run(NodeVector* roots) { |
1239 for (NodeVectorIter i = roots->begin(); i != roots->end(); ++i) { | 1237 for (Node* const root : *roots) { |
1240 ProcessQueue(*i); | 1238 ProcessQueue(root); |
1241 } | 1239 } |
1242 } | 1240 } |
1243 | 1241 |
1244 private: | 1242 private: |
1245 void ProcessQueue(Node* root) { | 1243 void ProcessQueue(Node* root) { |
1246 ZoneQueue<Node*>* queue = &(scheduler_->schedule_queue_); | 1244 ZoneQueue<Node*>* queue = &(scheduler_->schedule_queue_); |
1247 for (Node* node : root->inputs()) { | 1245 for (Node* node : root->inputs()) { |
1248 // Don't schedule coupled nodes on their own. | 1246 // Don't schedule coupled nodes on their own. |
1249 if (scheduler_->GetPlacement(node) == Scheduler::kCoupled) { | 1247 if (scheduler_->GetPlacement(node) == Scheduler::kCoupled) { |
1250 node = NodeProperties::GetControlInput(node); | 1248 node = NodeProperties::GetControlInput(node); |
(...skipping 146 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1397 | 1395 |
1398 // Serialize the assembly order and reverse-post-order numbering. | 1396 // Serialize the assembly order and reverse-post-order numbering. |
1399 special_rpo_->SerializeRPOIntoSchedule(); | 1397 special_rpo_->SerializeRPOIntoSchedule(); |
1400 special_rpo_->PrintAndVerifySpecialRPO(); | 1398 special_rpo_->PrintAndVerifySpecialRPO(); |
1401 | 1399 |
1402 // Add collected nodes for basic blocks to their blocks in the right order. | 1400 // Add collected nodes for basic blocks to their blocks in the right order. |
1403 int block_num = 0; | 1401 int block_num = 0; |
1404 for (NodeVector& nodes : scheduled_nodes_) { | 1402 for (NodeVector& nodes : scheduled_nodes_) { |
1405 BasicBlock::Id id = BasicBlock::Id::FromInt(block_num++); | 1403 BasicBlock::Id id = BasicBlock::Id::FromInt(block_num++); |
1406 BasicBlock* block = schedule_->GetBlockById(id); | 1404 BasicBlock* block = schedule_->GetBlockById(id); |
1407 for (NodeVectorRIter i = nodes.rbegin(); i != nodes.rend(); ++i) { | 1405 for (auto i = nodes.rbegin(); i != nodes.rend(); ++i) { |
1408 schedule_->AddNode(block, *i); | 1406 schedule_->AddNode(block, *i); |
1409 } | 1407 } |
1410 } | 1408 } |
1411 } | 1409 } |
1412 | 1410 |
1413 | 1411 |
1414 // ----------------------------------------------------------------------------- | 1412 // ----------------------------------------------------------------------------- |
1415 | 1413 |
1416 | 1414 |
1417 void Scheduler::FuseFloatingControl(BasicBlock* block, Node* node) { | 1415 void Scheduler::FuseFloatingControl(BasicBlock* block, Node* node) { |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1465 OFStream os(stdout); | 1463 OFStream os(stdout); |
1466 os << "Schedule after control flow fusion:\n" << *schedule_; | 1464 os << "Schedule after control flow fusion:\n" << *schedule_; |
1467 } | 1465 } |
1468 } | 1466 } |
1469 | 1467 |
1470 | 1468 |
1471 void Scheduler::MovePlannedNodes(BasicBlock* from, BasicBlock* to) { | 1469 void Scheduler::MovePlannedNodes(BasicBlock* from, BasicBlock* to) { |
1472 Trace("Move planned nodes from B%d to B%d\n", from->id().ToInt(), | 1470 Trace("Move planned nodes from B%d to B%d\n", from->id().ToInt(), |
1473 to->id().ToInt()); | 1471 to->id().ToInt()); |
1474 NodeVector* nodes = &(scheduled_nodes_[from->id().ToSize()]); | 1472 NodeVector* nodes = &(scheduled_nodes_[from->id().ToSize()]); |
1475 for (NodeVectorIter i = nodes->begin(); i != nodes->end(); ++i) { | 1473 for (Node* const node : *nodes) { |
1476 schedule_->SetBlockForNode(to, *i); | 1474 schedule_->SetBlockForNode(to, node); |
1477 scheduled_nodes_[to->id().ToSize()].push_back(*i); | 1475 scheduled_nodes_[to->id().ToSize()].push_back(node); |
1478 } | 1476 } |
1479 nodes->clear(); | 1477 nodes->clear(); |
1480 } | 1478 } |
1481 | 1479 |
1482 } // namespace compiler | 1480 } // namespace compiler |
1483 } // namespace internal | 1481 } // namespace internal |
1484 } // namespace v8 | 1482 } // namespace v8 |
OLD | NEW |