Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(388)

Side by Side Diff: src/compiler/scheduler.cc

Issue 851263002: [turbofan] Initial attempt to cleanup Node and related classes. (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 5 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/compiler/node-properties.cc ('k') | src/compiler/verifier.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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
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
OLDNEW
« no previous file with comments | « src/compiler/node-properties.cc ('k') | src/compiler/verifier.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698