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 129 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
140 break; | 140 break; |
141 } | 141 } |
142 default: | 142 default: |
143 DCHECK_EQ(Scheduler::kSchedulable, data->placement_); | 143 DCHECK_EQ(Scheduler::kSchedulable, data->placement_); |
144 DCHECK_EQ(Scheduler::kScheduled, placement); | 144 DCHECK_EQ(Scheduler::kScheduled, placement); |
145 break; | 145 break; |
146 } | 146 } |
147 // Reduce the use count of the node's inputs to potentially make them | 147 // Reduce the use count of the node's inputs to potentially make them |
148 // schedulable. If all the uses of a node have been scheduled, then the node | 148 // schedulable. If all the uses of a node have been scheduled, then the node |
149 // itself can be scheduled. | 149 // itself can be scheduled. |
150 for (InputIter i = node->inputs().begin(); i != node->inputs().end(); ++i) { | 150 for (Edge const edge : node->input_edges()) { |
151 DecrementUnscheduledUseCount(*i, i.index(), i.edge().from()); | 151 DecrementUnscheduledUseCount(edge.to(), edge.index(), edge.from()); |
152 } | 152 } |
153 } | 153 } |
154 data->placement_ = placement; | 154 data->placement_ = placement; |
155 } | 155 } |
156 | 156 |
157 | 157 |
158 bool Scheduler::IsCoupledControlEdge(Node* node, int index) { | 158 bool Scheduler::IsCoupledControlEdge(Node* node, int index) { |
159 return GetPlacement(node) == kCoupled && | 159 return GetPlacement(node) == kCoupled && |
160 NodeProperties::FirstControlIndex(node) == index; | 160 NodeProperties::FirstControlIndex(node) == index; |
161 } | 161 } |
(...skipping 286 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
448 } | 448 } |
449 | 449 |
450 void ConnectMerge(Node* merge) { | 450 void ConnectMerge(Node* merge) { |
451 // Don't connect the special merge at the end to its predecessors. | 451 // Don't connect the special merge at the end to its predecessors. |
452 if (IsFinalMerge(merge)) return; | 452 if (IsFinalMerge(merge)) return; |
453 | 453 |
454 BasicBlock* block = schedule_->block(merge); | 454 BasicBlock* block = schedule_->block(merge); |
455 DCHECK(block != NULL); | 455 DCHECK(block != NULL); |
456 // For all of the merge's control inputs, add a goto at the end to the | 456 // For all of the merge's control inputs, add a goto at the end to the |
457 // merge's basic block. | 457 // merge's basic block. |
458 for (InputIter j = merge->inputs().begin(); j != merge->inputs().end(); | 458 for (Node* const j : merge->inputs()) { |
459 ++j) { | 459 BasicBlock* predecessor_block = schedule_->block(j); |
460 BasicBlock* predecessor_block = schedule_->block(*j); | |
461 TraceConnect(merge, predecessor_block, block); | 460 TraceConnect(merge, predecessor_block, block); |
462 schedule_->AddGoto(predecessor_block, block); | 461 schedule_->AddGoto(predecessor_block, block); |
463 } | 462 } |
464 } | 463 } |
465 | 464 |
466 void ConnectReturn(Node* ret) { | 465 void ConnectReturn(Node* ret) { |
467 Node* return_block_node = NodeProperties::GetControlInput(ret); | 466 Node* return_block_node = NodeProperties::GetControlInput(ret); |
468 BasicBlock* return_block = schedule_->block(return_block_node); | 467 BasicBlock* return_block = schedule_->block(return_block_node); |
469 TraceConnect(ret, return_block, NULL); | 468 TraceConnect(ret, return_block, NULL); |
470 schedule_->AddReturn(return_block, ret); | 469 schedule_->AddReturn(return_block, ret); |
(...skipping 772 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1243 // Run the schedule late algorithm on a set of fixed root nodes. | 1242 // Run the schedule late algorithm on a set of fixed root nodes. |
1244 void Run(NodeVector* roots) { | 1243 void Run(NodeVector* roots) { |
1245 for (NodeVectorIter i = roots->begin(); i != roots->end(); ++i) { | 1244 for (NodeVectorIter i = roots->begin(); i != roots->end(); ++i) { |
1246 ProcessQueue(*i); | 1245 ProcessQueue(*i); |
1247 } | 1246 } |
1248 } | 1247 } |
1249 | 1248 |
1250 private: | 1249 private: |
1251 void ProcessQueue(Node* root) { | 1250 void ProcessQueue(Node* root) { |
1252 ZoneQueue<Node*>* queue = &(scheduler_->schedule_queue_); | 1251 ZoneQueue<Node*>* queue = &(scheduler_->schedule_queue_); |
1253 for (InputIter i = root->inputs().begin(); i != root->inputs().end(); ++i) { | 1252 for (Node* node : root->inputs()) { |
1254 Node* node = *i; | |
1255 | |
1256 // Don't schedule coupled nodes on their own. | 1253 // Don't schedule coupled nodes on their own. |
1257 if (scheduler_->GetPlacement(node) == Scheduler::kCoupled) { | 1254 if (scheduler_->GetPlacement(node) == Scheduler::kCoupled) { |
1258 node = NodeProperties::GetControlInput(node); | 1255 node = NodeProperties::GetControlInput(node); |
1259 } | 1256 } |
1260 | 1257 |
1261 // Test schedulability condition by looking at unscheduled use count. | 1258 // Test schedulability condition by looking at unscheduled use count. |
1262 if (scheduler_->GetData(node)->unscheduled_count_ != 0) continue; | 1259 if (scheduler_->GetData(node)->unscheduled_count_ != 0) continue; |
1263 | 1260 |
1264 queue->push(node); | 1261 queue->push(node); |
1265 while (!queue->empty()) { | 1262 while (!queue->empty()) { |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1318 return block->dominator(); | 1315 return block->dominator(); |
1319 } else if (block->loop_header() != NULL) { | 1316 } else if (block->loop_header() != NULL) { |
1320 return block->loop_header()->dominator(); | 1317 return block->loop_header()->dominator(); |
1321 } else { | 1318 } else { |
1322 return NULL; | 1319 return NULL; |
1323 } | 1320 } |
1324 } | 1321 } |
1325 | 1322 |
1326 BasicBlock* GetCommonDominatorOfUses(Node* node) { | 1323 BasicBlock* GetCommonDominatorOfUses(Node* node) { |
1327 BasicBlock* block = NULL; | 1324 BasicBlock* block = NULL; |
1328 Node::Uses uses = node->uses(); | 1325 for (Edge edge : node->use_edges()) { |
1329 for (Node::Uses::iterator i = uses.begin(); i != uses.end(); ++i) { | 1326 BasicBlock* use_block = GetBlockForUse(edge); |
1330 BasicBlock* use_block = GetBlockForUse(i.edge()); | |
1331 block = block == NULL ? use_block : use_block == NULL | 1327 block = block == NULL ? use_block : use_block == NULL |
1332 ? block | 1328 ? block |
1333 : scheduler_->GetCommonDominator( | 1329 : scheduler_->GetCommonDominator( |
1334 block, use_block); | 1330 block, use_block); |
1335 } | 1331 } |
1336 return block; | 1332 return block; |
1337 } | 1333 } |
1338 | 1334 |
1339 BasicBlock* GetBlockForUse(Node::Edge edge) { | 1335 BasicBlock* GetBlockForUse(Edge edge) { |
1340 Node* use = edge.from(); | 1336 Node* use = edge.from(); |
1341 IrOpcode::Value opcode = use->opcode(); | 1337 IrOpcode::Value opcode = use->opcode(); |
1342 if (opcode == IrOpcode::kPhi || opcode == IrOpcode::kEffectPhi) { | 1338 if (opcode == IrOpcode::kPhi || opcode == IrOpcode::kEffectPhi) { |
1343 // If the use is from a coupled (i.e. floating) phi, compute the common | 1339 // If the use is from a coupled (i.e. floating) phi, compute the common |
1344 // dominator of its uses. This will not recurse more than one level. | 1340 // dominator of its uses. This will not recurse more than one level. |
1345 if (scheduler_->GetPlacement(use) == Scheduler::kCoupled) { | 1341 if (scheduler_->GetPlacement(use) == Scheduler::kCoupled) { |
1346 Trace(" inspecting uses of coupled #%d:%s\n", use->id(), | 1342 Trace(" inspecting uses of coupled #%d:%s\n", use->id(), |
1347 use->op()->mnemonic()); | 1343 use->op()->mnemonic()); |
1348 DCHECK_EQ(edge.to(), NodeProperties::GetControlInput(use)); | 1344 DCHECK_EQ(edge.to(), NodeProperties::GetControlInput(use)); |
1349 return GetCommonDominatorOfUses(use); | 1345 return GetCommonDominatorOfUses(use); |
(...skipping 136 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1486 for (NodeVectorIter i = nodes->begin(); i != nodes->end(); ++i) { | 1482 for (NodeVectorIter i = nodes->begin(); i != nodes->end(); ++i) { |
1487 schedule_->SetBlockForNode(to, *i); | 1483 schedule_->SetBlockForNode(to, *i); |
1488 scheduled_nodes_[to->id().ToSize()].push_back(*i); | 1484 scheduled_nodes_[to->id().ToSize()].push_back(*i); |
1489 } | 1485 } |
1490 nodes->clear(); | 1486 nodes->clear(); |
1491 } | 1487 } |
1492 | 1488 |
1493 } // namespace compiler | 1489 } // namespace compiler |
1494 } // namespace internal | 1490 } // namespace internal |
1495 } // namespace v8 | 1491 } // namespace v8 |
OLD | NEW |