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 216 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
227 | 227 |
228 | 228 |
229 // ----------------------------------------------------------------------------- | 229 // ----------------------------------------------------------------------------- |
230 // Phase 1: Build control-flow graph. | 230 // Phase 1: Build control-flow graph. |
231 | 231 |
232 | 232 |
233 // Internal class to build a control flow graph (i.e the basic blocks and edges | 233 // Internal class to build a control flow graph (i.e the basic blocks and edges |
234 // between them within a Schedule) from the node graph. Visits control edges of | 234 // between them within a Schedule) from the node graph. Visits control edges of |
235 // the graph backwards from an end node in order to find the connected control | 235 // the graph backwards from an end node in order to find the connected control |
236 // subgraph, needed for scheduling. | 236 // subgraph, needed for scheduling. |
237 class CFGBuilder { | 237 class CFGBuilder : public ZoneObject { |
238 public: | 238 public: |
239 CFGBuilder(Zone* zone, Scheduler* scheduler) | 239 CFGBuilder(Zone* zone, Scheduler* scheduler) |
240 : scheduler_(scheduler), | 240 : scheduler_(scheduler), |
241 schedule_(scheduler->schedule_), | 241 schedule_(scheduler->schedule_), |
242 queue_(zone), | 242 queue_(zone), |
243 control_(zone), | 243 control_(zone), |
244 component_head_(NULL), | 244 component_head_(NULL), |
245 component_start_(NULL), | 245 component_start_(NULL), |
246 component_end_(NULL) {} | 246 component_end_(NULL) {} |
247 | 247 |
248 // Run the control flow graph construction algorithm by walking the graph | 248 // Run the control flow graph construction algorithm by walking the graph |
249 // backwards from end through control edges, building and connecting the | 249 // backwards from end through control edges, building and connecting the |
250 // basic blocks for control nodes. | 250 // basic blocks for control nodes. |
251 void Run() { | 251 void Run() { |
| 252 ResetDataStructures(); |
252 Queue(scheduler_->graph_->end()); | 253 Queue(scheduler_->graph_->end()); |
253 | 254 |
254 while (!queue_.empty()) { // Breadth-first backwards traversal. | 255 while (!queue_.empty()) { // Breadth-first backwards traversal. |
255 Node* node = queue_.front(); | 256 Node* node = queue_.front(); |
256 queue_.pop(); | 257 queue_.pop(); |
257 int max = NodeProperties::PastControlIndex(node); | 258 int max = NodeProperties::PastControlIndex(node); |
258 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { | 259 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { |
259 Queue(node->InputAt(i)); | 260 Queue(node->InputAt(i)); |
260 } | 261 } |
261 } | 262 } |
262 | 263 |
263 for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) { | 264 for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) { |
264 ConnectBlocks(*i); // Connect block to its predecessor/successors. | 265 ConnectBlocks(*i); // Connect block to its predecessor/successors. |
265 } | 266 } |
266 } | 267 } |
267 | 268 |
268 // Run the control flow graph construction for a minimal control-connected | 269 // Run the control flow graph construction for a minimal control-connected |
269 // component ending in {node} and merge that component into an existing | 270 // component ending in {node} and merge that component into an existing |
270 // control flow graph at the bottom of {block}. | 271 // control flow graph at the bottom of {block}. |
271 void Run(BasicBlock* block, Node* node) { | 272 void Run(BasicBlock* block, Node* node) { |
| 273 ResetDataStructures(); |
272 Queue(node); | 274 Queue(node); |
273 | 275 |
274 component_start_ = block; | 276 component_start_ = block; |
275 component_end_ = schedule_->block(node); | 277 component_end_ = schedule_->block(node); |
276 while (!queue_.empty()) { // Breadth-first backwards traversal. | 278 while (!queue_.empty()) { // Breadth-first backwards traversal. |
277 Node* node = queue_.front(); | 279 Node* node = queue_.front(); |
278 queue_.pop(); | 280 queue_.pop(); |
279 bool is_dom = true; | 281 bool is_dom = true; |
280 int max = NodeProperties::PastControlIndex(node); | 282 int max = NodeProperties::PastControlIndex(node); |
281 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { | 283 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { |
(...skipping 195 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
477 Trace("Connect #%d:%s, B%d -> B%d\n", node->id(), node->op()->mnemonic(), | 479 Trace("Connect #%d:%s, B%d -> B%d\n", node->id(), node->op()->mnemonic(), |
478 block->id().ToInt(), succ->id().ToInt()); | 480 block->id().ToInt(), succ->id().ToInt()); |
479 } | 481 } |
480 } | 482 } |
481 | 483 |
482 bool IsFinalMerge(Node* node) { | 484 bool IsFinalMerge(Node* node) { |
483 return (node->opcode() == IrOpcode::kMerge && | 485 return (node->opcode() == IrOpcode::kMerge && |
484 node == scheduler_->graph_->end()->InputAt(0)); | 486 node == scheduler_->graph_->end()->InputAt(0)); |
485 } | 487 } |
486 | 488 |
| 489 void ResetDataStructures() { |
| 490 control_.clear(); |
| 491 DCHECK(queue_.empty()); |
| 492 DCHECK(control_.empty()); |
| 493 } |
| 494 |
487 Scheduler* scheduler_; | 495 Scheduler* scheduler_; |
488 Schedule* schedule_; | 496 Schedule* schedule_; |
489 ZoneQueue<Node*> queue_; | 497 ZoneQueue<Node*> queue_; |
490 NodeVector control_; | 498 NodeVector control_; |
491 Node* component_head_; | 499 Node* component_head_; |
492 BasicBlock* component_start_; | 500 BasicBlock* component_start_; |
493 BasicBlock* component_end_; | 501 BasicBlock* component_end_; |
494 }; | 502 }; |
495 | 503 |
496 | 504 |
497 void Scheduler::BuildCFG() { | 505 void Scheduler::BuildCFG() { |
498 Trace("--- CREATING CFG -------------------------------------------\n"); | 506 Trace("--- CREATING CFG -------------------------------------------\n"); |
499 | 507 |
500 // Build a control-flow graph for the main control-connected component that | 508 // Build a control-flow graph for the main control-connected component that |
501 // is being spanned by the graph's start and end nodes. | 509 // is being spanned by the graph's start and end nodes. |
502 CFGBuilder cfg_builder(zone_, this); | 510 control_flow_builder_ = new (zone_) CFGBuilder(zone_, this); |
503 cfg_builder.Run(); | 511 control_flow_builder_->Run(); |
504 | 512 |
505 // Initialize per-block data. | 513 // Initialize per-block data. |
506 scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_)); | 514 scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_)); |
507 } | 515 } |
508 | 516 |
509 | 517 |
510 // ----------------------------------------------------------------------------- | 518 // ----------------------------------------------------------------------------- |
511 // Phase 2: Compute special RPO and dominator tree. | 519 // Phase 2: Compute special RPO and dominator tree. |
512 | 520 |
513 | 521 |
(...skipping 928 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1442 | 1450 |
1443 | 1451 |
1444 void Scheduler::FuseFloatingControl(BasicBlock* block, Node* node) { | 1452 void Scheduler::FuseFloatingControl(BasicBlock* block, Node* node) { |
1445 Trace("--- FUSE FLOATING CONTROL ----------------------------------\n"); | 1453 Trace("--- FUSE FLOATING CONTROL ----------------------------------\n"); |
1446 if (FLAG_trace_turbo_scheduler) { | 1454 if (FLAG_trace_turbo_scheduler) { |
1447 OFStream os(stdout); | 1455 OFStream os(stdout); |
1448 os << "Schedule before control flow fusion:\n" << *schedule_; | 1456 os << "Schedule before control flow fusion:\n" << *schedule_; |
1449 } | 1457 } |
1450 | 1458 |
1451 // Iterate on phase 1: Build control-flow graph. | 1459 // Iterate on phase 1: Build control-flow graph. |
1452 CFGBuilder cfg_builder(zone_, this); | 1460 control_flow_builder_->Run(block, node); |
1453 cfg_builder.Run(block, node); | |
1454 | 1461 |
1455 // Iterate on phase 2: Compute special RPO and dominator tree. | 1462 // Iterate on phase 2: Compute special RPO and dominator tree. |
1456 special_rpo_->UpdateSpecialRPO(block, schedule_->block(node)); | 1463 special_rpo_->UpdateSpecialRPO(block, schedule_->block(node)); |
1457 // TODO(mstarzinger): Currently "iterate on" means "re-run". Fix that. | 1464 // TODO(mstarzinger): Currently "iterate on" means "re-run". Fix that. |
1458 for (BasicBlock* block : schedule_->all_blocks_) { | 1465 for (BasicBlock* block : schedule_->all_blocks_) { |
1459 block->set_dominator_depth(-1); | 1466 block->set_dominator_depth(-1); |
1460 block->set_dominator(NULL); | 1467 block->set_dominator(NULL); |
1461 } | 1468 } |
1462 GenerateImmediateDominatorTree(); | 1469 GenerateImmediateDominatorTree(); |
1463 | 1470 |
1464 // Iterate on phase 4: Schedule nodes early. | 1471 // Iterate on phase 4: Schedule nodes early. |
1465 // TODO(mstarzinger): The following loop gathering the propagation roots is a | 1472 // TODO(mstarzinger): The following loop gathering the propagation roots is a |
1466 // temporary solution and should be merged into the rest of the scheduler as | 1473 // temporary solution and should be merged into the rest of the scheduler as |
1467 // soon as the approach settled for all floating loops. | 1474 // soon as the approach settled for all floating loops. |
1468 NodeVector propagation_roots(cfg_builder.control_); | 1475 NodeVector propagation_roots(control_flow_builder_->control_); |
1469 for (Node* node : cfg_builder.control_) { | 1476 for (Node* node : control_flow_builder_->control_) { |
1470 for (Node* use : node->uses()) { | 1477 for (Node* use : node->uses()) { |
1471 if (use->opcode() == IrOpcode::kPhi || | 1478 if (use->opcode() == IrOpcode::kPhi || |
1472 use->opcode() == IrOpcode::kEffectPhi) { | 1479 use->opcode() == IrOpcode::kEffectPhi) { |
1473 propagation_roots.push_back(use); | 1480 propagation_roots.push_back(use); |
1474 } | 1481 } |
1475 } | 1482 } |
1476 } | 1483 } |
1477 if (FLAG_trace_turbo_scheduler) { | 1484 if (FLAG_trace_turbo_scheduler) { |
1478 Trace("propagation roots: "); | 1485 Trace("propagation roots: "); |
1479 for (Node* node : propagation_roots) { | 1486 for (Node* node : propagation_roots) { |
(...skipping 23 matching lines...) Expand all Loading... |
1503 for (NodeVectorIter i = nodes->begin(); i != nodes->end(); ++i) { | 1510 for (NodeVectorIter i = nodes->begin(); i != nodes->end(); ++i) { |
1504 schedule_->SetBlockForNode(to, *i); | 1511 schedule_->SetBlockForNode(to, *i); |
1505 scheduled_nodes_[to->id().ToSize()].push_back(*i); | 1512 scheduled_nodes_[to->id().ToSize()].push_back(*i); |
1506 } | 1513 } |
1507 nodes->clear(); | 1514 nodes->clear(); |
1508 } | 1515 } |
1509 | 1516 |
1510 } // namespace compiler | 1517 } // namespace compiler |
1511 } // namespace internal | 1518 } // namespace internal |
1512 } // namespace v8 | 1519 } // namespace v8 |
OLD | NEW |