| 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 "src/compiler/scheduler.h" | 5 #include "src/compiler/scheduler.h" |
| 6 | 6 |
| 7 #include "src/bit-vector.h" | 7 #include "src/bit-vector.h" |
| 8 #include "src/compiler/common-operator.h" | 8 #include "src/compiler/common-operator.h" |
| 9 #include "src/compiler/control-equivalence.h" | 9 #include "src/compiler/control-equivalence.h" |
| 10 #include "src/compiler/graph.h" | 10 #include "src/compiler/graph.h" |
| (...skipping 248 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 259 component_end_ = schedule_->block(exit); | 259 component_end_ = schedule_->block(exit); |
| 260 scheduler_->equivalence_->Run(exit); | 260 scheduler_->equivalence_->Run(exit); |
| 261 while (!queue_.empty()) { // Breadth-first backwards traversal. | 261 while (!queue_.empty()) { // Breadth-first backwards traversal. |
| 262 Node* node = queue_.front(); | 262 Node* node = queue_.front(); |
| 263 queue_.pop(); | 263 queue_.pop(); |
| 264 | 264 |
| 265 // Use control dependence equivalence to find a canonical single-entry | 265 // Use control dependence equivalence to find a canonical single-entry |
| 266 // single-exit region that makes up a minimal component to be scheduled. | 266 // single-exit region that makes up a minimal component to be scheduled. |
| 267 if (IsSingleEntrySingleExitRegion(node, exit)) { | 267 if (IsSingleEntrySingleExitRegion(node, exit)) { |
| 268 Trace("Found SESE at #%d:%s\n", node->id(), node->op()->mnemonic()); | 268 Trace("Found SESE at #%d:%s\n", node->id(), node->op()->mnemonic()); |
| 269 DCHECK_EQ(NULL, component_entry_); | 269 DCHECK(!component_entry_); |
| 270 component_entry_ = node; | 270 component_entry_ = node; |
| 271 continue; | 271 continue; |
| 272 } | 272 } |
| 273 | 273 |
| 274 int max = NodeProperties::PastControlIndex(node); | 274 int max = NodeProperties::PastControlIndex(node); |
| 275 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { | 275 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { |
| 276 Queue(node->InputAt(i)); | 276 Queue(node->InputAt(i)); |
| 277 } | 277 } |
| 278 } | 278 } |
| 279 DCHECK_NE(NULL, component_entry_); | 279 DCHECK(component_entry_); |
| 280 | 280 |
| 281 for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) { | 281 for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) { |
| 282 ConnectBlocks(*i); // Connect block to its predecessor/successors. | 282 ConnectBlocks(*i); // Connect block to its predecessor/successors. |
| 283 } | 283 } |
| 284 } | 284 } |
| 285 | 285 |
| 286 private: | 286 private: |
| 287 // TODO(mstarzinger): Only for Scheduler::FuseFloatingControl. | 287 // TODO(mstarzinger): Only for Scheduler::FuseFloatingControl. |
| 288 friend class Scheduler; | 288 friend class Scheduler; |
| 289 | 289 |
| (...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 363 // Collect the branch-related projections from a node, such as IfTrue, | 363 // Collect the branch-related projections from a node, such as IfTrue, |
| 364 // IfFalse. | 364 // IfFalse. |
| 365 // TODO(titzer): consider moving this to node.h | 365 // TODO(titzer): consider moving this to node.h |
| 366 void CollectSuccessorProjections(Node* node, Node** buffer, | 366 void CollectSuccessorProjections(Node* node, Node** buffer, |
| 367 IrOpcode::Value true_opcode, | 367 IrOpcode::Value true_opcode, |
| 368 IrOpcode::Value false_opcode) { | 368 IrOpcode::Value false_opcode) { |
| 369 buffer[0] = NULL; | 369 buffer[0] = NULL; |
| 370 buffer[1] = NULL; | 370 buffer[1] = NULL; |
| 371 for (Node* use : node->uses()) { | 371 for (Node* use : node->uses()) { |
| 372 if (use->opcode() == true_opcode) { | 372 if (use->opcode() == true_opcode) { |
| 373 DCHECK_EQ(NULL, buffer[0]); | 373 DCHECK(!buffer[0]); |
| 374 buffer[0] = use; | 374 buffer[0] = use; |
| 375 } | 375 } |
| 376 if (use->opcode() == false_opcode) { | 376 if (use->opcode() == false_opcode) { |
| 377 DCHECK_EQ(NULL, buffer[1]); | 377 DCHECK(!buffer[1]); |
| 378 buffer[1] = use; | 378 buffer[1] = use; |
| 379 } | 379 } |
| 380 } | 380 } |
| 381 DCHECK_NE(NULL, buffer[0]); | 381 DCHECK(buffer[0]); |
| 382 DCHECK_NE(NULL, buffer[1]); | 382 DCHECK(buffer[1]); |
| 383 } | 383 } |
| 384 | 384 |
| 385 void CollectSuccessorBlocks(Node* node, BasicBlock** buffer, | 385 void CollectSuccessorBlocks(Node* node, BasicBlock** buffer, |
| 386 IrOpcode::Value true_opcode, | 386 IrOpcode::Value true_opcode, |
| 387 IrOpcode::Value false_opcode) { | 387 IrOpcode::Value false_opcode) { |
| 388 Node* successors[2]; | 388 Node* successors[2]; |
| 389 CollectSuccessorProjections(node, successors, true_opcode, false_opcode); | 389 CollectSuccessorProjections(node, successors, true_opcode, false_opcode); |
| 390 buffer[0] = schedule_->block(successors[0]); | 390 buffer[0] = schedule_->block(successors[0]); |
| 391 buffer[1] = schedule_->block(successors[1]); | 391 buffer[1] = schedule_->block(successors[1]); |
| 392 } | 392 } |
| (...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 441 } | 441 } |
| 442 | 442 |
| 443 void ConnectReturn(Node* ret) { | 443 void ConnectReturn(Node* ret) { |
| 444 Node* return_block_node = NodeProperties::GetControlInput(ret); | 444 Node* return_block_node = NodeProperties::GetControlInput(ret); |
| 445 BasicBlock* return_block = schedule_->block(return_block_node); | 445 BasicBlock* return_block = schedule_->block(return_block_node); |
| 446 TraceConnect(ret, return_block, NULL); | 446 TraceConnect(ret, return_block, NULL); |
| 447 schedule_->AddReturn(return_block, ret); | 447 schedule_->AddReturn(return_block, ret); |
| 448 } | 448 } |
| 449 | 449 |
| 450 void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) { | 450 void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) { |
| 451 DCHECK_NE(NULL, block); | 451 DCHECK(block); |
| 452 if (succ == NULL) { | 452 if (succ == NULL) { |
| 453 Trace("Connect #%d:%s, B%d -> end\n", node->id(), node->op()->mnemonic(), | 453 Trace("Connect #%d:%s, B%d -> end\n", node->id(), node->op()->mnemonic(), |
| 454 block->id().ToInt()); | 454 block->id().ToInt()); |
| 455 } else { | 455 } else { |
| 456 Trace("Connect #%d:%s, B%d -> B%d\n", node->id(), node->op()->mnemonic(), | 456 Trace("Connect #%d:%s, B%d -> B%d\n", node->id(), node->op()->mnemonic(), |
| 457 block->id().ToInt(), succ->id().ToInt()); | 457 block->id().ToInt(), succ->id().ToInt()); |
| 458 } | 458 } |
| 459 } | 459 } |
| 460 | 460 |
| 461 bool IsFinalMerge(Node* node) { | 461 bool IsFinalMerge(Node* node) { |
| (...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 526 beyond_end_(NULL), | 526 beyond_end_(NULL), |
| 527 loops_(zone), | 527 loops_(zone), |
| 528 backedges_(zone), | 528 backedges_(zone), |
| 529 stack_(zone), | 529 stack_(zone), |
| 530 previous_block_count_(0) {} | 530 previous_block_count_(0) {} |
| 531 | 531 |
| 532 // Computes the special reverse-post-order for the main control flow graph, | 532 // Computes the special reverse-post-order for the main control flow graph, |
| 533 // that is for the graph spanned between the schedule's start and end blocks. | 533 // that is for the graph spanned between the schedule's start and end blocks. |
| 534 void ComputeSpecialRPO() { | 534 void ComputeSpecialRPO() { |
| 535 DCHECK(schedule_->end()->SuccessorCount() == 0); | 535 DCHECK(schedule_->end()->SuccessorCount() == 0); |
| 536 DCHECK_EQ(NULL, order_); // Main order does not exist yet. | 536 DCHECK(!order_); // Main order does not exist yet. |
| 537 ComputeAndInsertSpecialRPO(schedule_->start(), schedule_->end()); | 537 ComputeAndInsertSpecialRPO(schedule_->start(), schedule_->end()); |
| 538 } | 538 } |
| 539 | 539 |
| 540 // Computes the special reverse-post-order for a partial control flow graph, | 540 // Computes the special reverse-post-order for a partial control flow graph, |
| 541 // that is for the graph spanned between the given {entry} and {end} blocks, | 541 // that is for the graph spanned between the given {entry} and {end} blocks, |
| 542 // then updates the existing ordering with this new information. | 542 // then updates the existing ordering with this new information. |
| 543 void UpdateSpecialRPO(BasicBlock* entry, BasicBlock* end) { | 543 void UpdateSpecialRPO(BasicBlock* entry, BasicBlock* end) { |
| 544 DCHECK_NE(NULL, order_); // Main order to be updated is present. | 544 DCHECK(order_); // Main order to be updated is present. |
| 545 ComputeAndInsertSpecialRPO(entry, end); | 545 ComputeAndInsertSpecialRPO(entry, end); |
| 546 } | 546 } |
| 547 | 547 |
| 548 // Serialize the previously computed order as a special reverse-post-order | 548 // Serialize the previously computed order as a special reverse-post-order |
| 549 // numbering for basic blocks into the final schedule. | 549 // numbering for basic blocks into the final schedule. |
| 550 void SerializeRPOIntoSchedule() { | 550 void SerializeRPOIntoSchedule() { |
| 551 int32_t number = 0; | 551 int32_t number = 0; |
| 552 for (BasicBlock* b = order_; b != NULL; b = b->rpo_next()) { | 552 for (BasicBlock* b = order_; b != NULL; b = b->rpo_next()) { |
| 553 b->set_rpo_number(number++); | 553 b->set_rpo_number(number++); |
| 554 schedule_->rpo_order()->push_back(b); | 554 schedule_->rpo_order()->push_back(b); |
| (...skipping 911 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1466 for (Node* const node : *nodes) { | 1466 for (Node* const node : *nodes) { |
| 1467 schedule_->SetBlockForNode(to, node); | 1467 schedule_->SetBlockForNode(to, node); |
| 1468 scheduled_nodes_[to->id().ToSize()].push_back(node); | 1468 scheduled_nodes_[to->id().ToSize()].push_back(node); |
| 1469 } | 1469 } |
| 1470 nodes->clear(); | 1470 nodes->clear(); |
| 1471 } | 1471 } |
| 1472 | 1472 |
| 1473 } // namespace compiler | 1473 } // namespace compiler |
| 1474 } // namespace internal | 1474 } // namespace internal |
| 1475 } // namespace v8 | 1475 } // namespace v8 |
| OLD | NEW |