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

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

Issue 706123003: Make scheduler handle floating non-naked loops. (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Fix Win64 build. Created 6 years, 1 month 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 | Annotate | Revision Log
« no previous file with comments | « no previous file | test/cctest/compiler/test-scheduler.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 667 matching lines...) Expand 10 before | Expand all | Expand 10 after
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
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
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
OLDNEW
« no previous file with comments | « no previous file | test/cctest/compiler/test-scheduler.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698