| 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 |