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 667 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
678 BlockList* insert_before = order_->FindForBlock(entry); | 678 BlockList* insert_before = order_->FindForBlock(entry); |
679 BlockList* insert_after = insert_before ? insert_before->next : NULL; | 679 BlockList* insert_after = insert_before ? insert_before->next : NULL; |
680 BlockList* order = insert_after; | 680 BlockList* order = insert_after; |
681 | 681 |
682 // Perform an iterative RPO traversal using an explicit stack, | 682 // Perform an iterative RPO traversal using an explicit stack, |
683 // recording backedges that form cycles. O(|B|). | 683 // recording backedges that form cycles. O(|B|). |
684 DCHECK_LT(previous_block_count_, schedule_->BasicBlockCount()); | 684 DCHECK_LT(previous_block_count_, schedule_->BasicBlockCount()); |
685 stack_.resize(schedule_->BasicBlockCount() - previous_block_count_); | 685 stack_.resize(schedule_->BasicBlockCount() - previous_block_count_); |
686 previous_block_count_ = schedule_->BasicBlockCount(); | 686 previous_block_count_ = schedule_->BasicBlockCount(); |
687 int stack_depth = Push(stack_, 0, entry, kBlockUnvisited1); | 687 int stack_depth = Push(stack_, 0, entry, kBlockUnvisited1); |
688 int num_loops = 0; | 688 int num_loops = static_cast<int>(loops_.size()); |
689 | 689 |
690 while (stack_depth > 0) { | 690 while (stack_depth > 0) { |
691 int current = stack_depth - 1; | 691 int current = stack_depth - 1; |
692 SpecialRPOStackFrame* frame = &stack_[current]; | 692 SpecialRPOStackFrame* frame = &stack_[current]; |
693 | 693 |
694 if (frame->block != end && | 694 if (frame->block != end && |
695 frame->index < frame->block->SuccessorCount()) { | 695 frame->index < frame->block->SuccessorCount()) { |
696 // Process the next successor. | 696 // Process the next successor. |
697 BasicBlock* succ = frame->block->SuccessorAt(frame->index++); | 697 BasicBlock* succ = frame->block->SuccessorAt(frame->index++); |
698 if (succ->rpo_number() == kBlockVisited1) continue; | 698 if (succ->rpo_number() == kBlockVisited1) continue; |
(...skipping 11 matching lines...) Expand all Loading... |
710 } | 710 } |
711 } else { | 711 } else { |
712 // Finished with all successors; pop the stack and add the block. | 712 // Finished with all successors; pop the stack and add the block. |
713 order = order->Add(zone_, frame->block); | 713 order = order->Add(zone_, frame->block); |
714 frame->block->set_rpo_number(kBlockVisited1); | 714 frame->block->set_rpo_number(kBlockVisited1); |
715 stack_depth--; | 715 stack_depth--; |
716 } | 716 } |
717 } | 717 } |
718 | 718 |
719 // If no loops were encountered, then the order we computed was correct. | 719 // If no loops were encountered, then the order we computed was correct. |
720 if (num_loops != 0) { | 720 if (num_loops > static_cast<int>(loops_.size())) { |
721 // Otherwise, compute the loop information from the backedges in order | 721 // Otherwise, compute the loop information from the backedges in order |
722 // to perform a traversal that groups loop bodies together. | 722 // to perform a traversal that groups loop bodies together. |
723 ComputeLoopInfo(stack_, num_loops, &backedges_); | 723 ComputeLoopInfo(stack_, num_loops, &backedges_); |
724 | 724 |
725 // Initialize the "loop stack". Note the entry could be a loop header. | 725 // Initialize the "loop stack". Note the entry could be a loop header. |
726 LoopInfo* loop = | 726 LoopInfo* loop = |
727 HasLoopNumber(entry) ? &loops_[GetLoopNumber(entry)] : NULL; | 727 HasLoopNumber(entry) ? &loops_[GetLoopNumber(entry)] : NULL; |
728 order = NULL; | 728 order = insert_after; |
729 | 729 |
730 // Perform an iterative post-order traversal, visiting loop bodies before | 730 // Perform an iterative post-order traversal, visiting loop bodies before |
731 // edges that lead out of loops. Visits each block once, but linking loop | 731 // edges that lead out of loops. Visits each block once, but linking loop |
732 // sections together is linear in the loop size, so overall is | 732 // sections together is linear in the loop size, so overall is |
733 // O(|B| + max(loop_depth) * max(|loop|)) | 733 // O(|B| + max(loop_depth) * max(|loop|)) |
734 stack_depth = Push(stack_, 0, entry, kBlockUnvisited2); | 734 stack_depth = Push(stack_, 0, entry, kBlockUnvisited2); |
735 while (stack_depth > 0) { | 735 while (stack_depth > 0) { |
736 SpecialRPOStackFrame* frame = &stack_[stack_depth - 1]; | 736 SpecialRPOStackFrame* frame = &stack_[stack_depth - 1]; |
737 BasicBlock* block = frame->block; | 737 BasicBlock* block = frame->block; |
738 BasicBlock* succ = NULL; | 738 BasicBlock* succ = NULL; |
739 | 739 |
740 if (frame->index < block->SuccessorCount()) { | 740 if (block != end && frame->index < block->SuccessorCount()) { |
741 // Process the next normal successor. | 741 // Process the next normal successor. |
742 succ = block->SuccessorAt(frame->index++); | 742 succ = block->SuccessorAt(frame->index++); |
743 } else if (HasLoopNumber(block)) { | 743 } else if (HasLoopNumber(block)) { |
744 // Process additional outgoing edges from the loop header. | 744 // Process additional outgoing edges from the loop header. |
745 if (block->rpo_number() == kBlockOnStack) { | 745 if (block->rpo_number() == kBlockOnStack) { |
746 // Finish the loop body the first time the header is left on the | 746 // Finish the loop body the first time the header is left on the |
747 // stack. | 747 // stack. |
748 DCHECK(loop != NULL && loop->header == block); | 748 DCHECK(loop != NULL && loop->header == block); |
749 loop->start = order->Add(zone_, block); | 749 loop->start = order->Add(zone_, block); |
750 order = loop->end; | 750 order = loop->end; |
(...skipping 723 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1474 for (NodeVectorIter i = nodes->begin(); i != nodes->end(); ++i) { | 1474 for (NodeVectorIter i = nodes->begin(); i != nodes->end(); ++i) { |
1475 schedule_->SetBlockForNode(to, *i); | 1475 schedule_->SetBlockForNode(to, *i); |
1476 scheduled_nodes_[to->id().ToSize()].push_back(*i); | 1476 scheduled_nodes_[to->id().ToSize()].push_back(*i); |
1477 } | 1477 } |
1478 nodes->clear(); | 1478 nodes->clear(); |
1479 } | 1479 } |
1480 | 1480 |
1481 } // namespace compiler | 1481 } // namespace compiler |
1482 } // namespace internal | 1482 } // namespace internal |
1483 } // namespace v8 | 1483 } // namespace v8 |
OLD | NEW |