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/compiler/graph.h" | 10 #include "src/compiler/graph.h" |
(...skipping 544 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
555 } | 555 } |
556 stack_depth--; | 556 stack_depth--; |
557 } | 557 } |
558 } | 558 } |
559 } | 559 } |
560 | 560 |
561 // Construct the final order from the list. | 561 // Construct the final order from the list. |
562 BasicBlockVector* final_order = schedule_->rpo_order(); | 562 BasicBlockVector* final_order = schedule_->rpo_order(); |
563 order->Serialize(final_order); | 563 order->Serialize(final_order); |
564 | 564 |
565 // Compute the correct loop header for every block and set the correct loop | 565 // Compute the correct loop headers and set the correct loop ends. |
566 // ends. | |
567 LoopInfo* current_loop = NULL; | 566 LoopInfo* current_loop = NULL; |
568 BasicBlock* current_header = NULL; | 567 BasicBlock* current_header = NULL; |
569 int loop_depth = 0; | 568 int loop_depth = 0; |
570 for (BasicBlockVectorIter i = final_order->begin(); i != final_order->end(); | 569 for (BasicBlockVectorIter i = final_order->begin(); i != final_order->end(); |
571 ++i) { | 570 ++i) { |
572 BasicBlock* current = *i; | 571 BasicBlock* current = *i; |
| 572 |
| 573 // Finish the previous loop(s) if we just exited them. |
| 574 while (current_header != NULL && |
| 575 current->rpo_number() >= current_header->loop_end()) { |
| 576 DCHECK(current_header->IsLoopHeader()); |
| 577 DCHECK(current_loop != NULL); |
| 578 current_loop = current_loop->prev; |
| 579 current_header = current_loop == NULL ? NULL : current_loop->header; |
| 580 --loop_depth; |
| 581 } |
573 current->set_loop_header(current_header); | 582 current->set_loop_header(current_header); |
| 583 |
| 584 // Push a new loop onto the stack if this loop is a loop header. |
574 if (current->IsLoopHeader()) { | 585 if (current->IsLoopHeader()) { |
575 loop_depth++; | 586 loop_depth++; |
576 current_loop = &loops[current->loop_end()]; | 587 current_loop = &loops[current->loop_end()]; |
577 BlockList* end = current_loop->end; | 588 BlockList* end = current_loop->end; |
578 current->set_loop_end(end == NULL | 589 current->set_loop_end(end == NULL |
579 ? static_cast<int>(final_order->size()) | 590 ? static_cast<int>(final_order->size()) |
580 : end->block->rpo_number()); | 591 : end->block->rpo_number()); |
581 current_header = current_loop->header; | 592 current_header = current_loop->header; |
582 Trace("B%d is a loop header, increment loop depth to %d\n", | 593 Trace("B%d is a loop header, increment loop depth to %d\n", |
583 current->id().ToInt(), loop_depth); | 594 current->id().ToInt(), loop_depth); |
584 } else { | |
585 while (current_header != NULL && | |
586 current->rpo_number() >= current_header->loop_end()) { | |
587 DCHECK(current_header->IsLoopHeader()); | |
588 DCHECK(current_loop != NULL); | |
589 current_loop = current_loop->prev; | |
590 current_header = current_loop == NULL ? NULL : current_loop->header; | |
591 --loop_depth; | |
592 } | |
593 } | 595 } |
| 596 |
594 current->set_loop_depth(loop_depth); | 597 current->set_loop_depth(loop_depth); |
| 598 |
595 if (current->loop_header() == NULL) { | 599 if (current->loop_header() == NULL) { |
596 Trace("B%d is not in a loop (depth == %d)\n", current->id().ToInt(), | 600 Trace("B%d is not in a loop (depth == %d)\n", current->id().ToInt(), |
597 current->loop_depth()); | 601 current->loop_depth()); |
598 } else { | 602 } else { |
599 Trace("B%d has loop header B%d, (depth == %d)\n", current->id().ToInt(), | 603 Trace("B%d has loop header B%d, (depth == %d)\n", current->id().ToInt(), |
600 current->loop_header()->id().ToInt(), current->loop_depth()); | 604 current->loop_header()->id().ToInt(), current->loop_depth()); |
601 } | 605 } |
602 } | 606 } |
603 | 607 |
604 // Compute the assembly order (non-deferred code first, deferred code | 608 // Compute the assembly order (non-deferred code first, deferred code |
(...skipping 144 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
749 bool membership = loops[j].members->Contains(bid.ToInt()); | 753 bool membership = loops[j].members->Contains(bid.ToInt()); |
750 bool range = loops[j].header->LoopContains(block); | 754 bool range = loops[j].header->LoopContains(block); |
751 os << (membership ? " |" : " "); | 755 os << (membership ? " |" : " "); |
752 os << (range ? "x" : " "); | 756 os << (range ? "x" : " "); |
753 } | 757 } |
754 os << " B" << bid << ": "; | 758 os << " B" << bid << ": "; |
755 if (block->loop_end() >= 0) { | 759 if (block->loop_end() >= 0) { |
756 os << " range: [" << block->rpo_number() << ", " << block->loop_end() | 760 os << " range: [" << block->rpo_number() << ", " << block->loop_end() |
757 << ")"; | 761 << ")"; |
758 } | 762 } |
| 763 if (block->loop_header() != NULL) { |
| 764 os << " header: B" << block->loop_header()->id(); |
| 765 } |
| 766 if (block->loop_depth() > 0) { |
| 767 os << " depth: " << block->loop_depth(); |
| 768 } |
759 os << "\n"; | 769 os << "\n"; |
760 } | 770 } |
761 } | 771 } |
762 | 772 |
763 void VerifySpecialRPO(int num_loops, LoopInfo* loops, | 773 void VerifySpecialRPO(int num_loops, LoopInfo* loops, |
764 BasicBlockVector* order) { | 774 BasicBlockVector* order) { |
765 DCHECK(order->size() > 0); | 775 DCHECK(order->size() > 0); |
766 DCHECK((*order)[0]->id().ToInt() == 0); // entry should be first. | 776 DCHECK((*order)[0]->id().ToInt() == 0); // entry should be first. |
767 | 777 |
768 for (int i = 0; i < num_loops; i++) { | 778 for (int i = 0; i < num_loops; i++) { |
769 LoopInfo* loop = &loops[i]; | 779 LoopInfo* loop = &loops[i]; |
770 BasicBlock* header = loop->header; | 780 BasicBlock* header = loop->header; |
771 | 781 |
772 DCHECK(header != NULL); | 782 DCHECK(header != NULL); |
773 DCHECK(header->rpo_number() >= 0); | 783 DCHECK(header->rpo_number() >= 0); |
774 DCHECK(header->rpo_number() < static_cast<int>(order->size())); | 784 DCHECK(header->rpo_number() < static_cast<int>(order->size())); |
775 DCHECK(header->loop_end() >= 0); | 785 DCHECK(header->loop_end() >= 0); |
776 DCHECK(header->loop_end() <= static_cast<int>(order->size())); | 786 DCHECK(header->loop_end() <= static_cast<int>(order->size())); |
777 DCHECK(header->loop_end() > header->rpo_number()); | 787 DCHECK(header->loop_end() > header->rpo_number()); |
| 788 DCHECK(header->loop_header() != header); |
778 | 789 |
779 // Verify the start ... end list relationship. | 790 // Verify the start ... end list relationship. |
780 int links = 0; | 791 int links = 0; |
781 BlockList* l = loop->start; | 792 BlockList* l = loop->start; |
782 DCHECK(l != NULL && l->block == header); | 793 DCHECK(l != NULL && l->block == header); |
783 bool end_found; | 794 bool end_found; |
784 while (true) { | 795 while (true) { |
785 if (l == NULL || l == loop->end) { | 796 if (l == NULL || l == loop->end) { |
786 end_found = (loop->end == l); | 797 end_found = (loop->end == l); |
787 break; | 798 break; |
(...skipping 279 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1067 DCHECK_NOT_NULL(block); | 1078 DCHECK_NOT_NULL(block); |
1068 | 1079 |
1069 int min_rpo = scheduler_->GetData(node)->minimum_block_->rpo_number(); | 1080 int min_rpo = scheduler_->GetData(node)->minimum_block_->rpo_number(); |
1070 Trace("Schedule late of #%d:%s is B%d at loop depth %d, minimum_rpo = %d\n", | 1081 Trace("Schedule late of #%d:%s is B%d at loop depth %d, minimum_rpo = %d\n", |
1071 node->id(), node->op()->mnemonic(), block->id().ToInt(), | 1082 node->id(), node->op()->mnemonic(), block->id().ToInt(), |
1072 block->loop_depth(), min_rpo); | 1083 block->loop_depth(), min_rpo); |
1073 | 1084 |
1074 // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively | 1085 // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively |
1075 // into enclosing loop pre-headers until they would preceed their | 1086 // into enclosing loop pre-headers until they would preceed their |
1076 // ScheduleEarly position. | 1087 // ScheduleEarly position. |
1077 BasicBlock* hoist_block = block; | 1088 BasicBlock* hoist_block = GetPreHeader(block); |
1078 while (hoist_block != NULL && hoist_block->rpo_number() >= min_rpo) { | 1089 while (hoist_block != NULL && hoist_block->rpo_number() >= min_rpo) { |
1079 if (hoist_block->loop_depth() < block->loop_depth()) { | 1090 Trace(" hoisting #%d:%s to block %d\n", node->id(), |
1080 block = hoist_block; | 1091 node->op()->mnemonic(), hoist_block->id().ToInt()); |
1081 Trace(" hoisting #%d:%s to block %d\n", node->id(), | 1092 DCHECK_LT(hoist_block->loop_depth(), block->loop_depth()); |
1082 node->op()->mnemonic(), block->id().ToInt()); | 1093 block = hoist_block; |
1083 } | 1094 hoist_block = GetPreHeader(hoist_block); |
1084 // Try to hoist to the pre-header of the loop header. | |
1085 hoist_block = hoist_block->loop_header(); | |
1086 if (hoist_block != NULL) { | |
1087 BasicBlock* pre_header = hoist_block->dominator(); | |
1088 DCHECK(pre_header == NULL || | |
1089 *hoist_block->predecessors_begin() == pre_header); | |
1090 Trace( | |
1091 " hoist to pre-header B%d of loop header B%d, depth would be %d\n", | |
1092 pre_header->id().ToInt(), hoist_block->id().ToInt(), | |
1093 pre_header->loop_depth()); | |
1094 hoist_block = pre_header; | |
1095 } | |
1096 } | 1095 } |
1097 | 1096 |
1098 ScheduleNode(block, node); | 1097 ScheduleNode(block, node); |
1099 } | 1098 } |
1100 | 1099 |
1101 private: | 1100 private: |
| 1101 BasicBlock* GetPreHeader(BasicBlock* block) { |
| 1102 if (block->IsLoopHeader()) { |
| 1103 return block->dominator(); |
| 1104 } else if (block->loop_header() != NULL) { |
| 1105 return block->loop_header()->dominator(); |
| 1106 } else { |
| 1107 return NULL; |
| 1108 } |
| 1109 } |
| 1110 |
1102 BasicBlock* GetCommonDominatorOfUses(Node* node) { | 1111 BasicBlock* GetCommonDominatorOfUses(Node* node) { |
1103 BasicBlock* block = NULL; | 1112 BasicBlock* block = NULL; |
1104 Node::Uses uses = node->uses(); | 1113 Node::Uses uses = node->uses(); |
1105 for (Node::Uses::iterator i = uses.begin(); i != uses.end(); ++i) { | 1114 for (Node::Uses::iterator i = uses.begin(); i != uses.end(); ++i) { |
1106 BasicBlock* use_block = GetBlockForUse(i.edge()); | 1115 BasicBlock* use_block = GetBlockForUse(i.edge()); |
1107 block = block == NULL ? use_block : use_block == NULL | 1116 block = block == NULL ? use_block : use_block == NULL |
1108 ? block | 1117 ? block |
1109 : scheduler_->GetCommonDominator( | 1118 : scheduler_->GetCommonDominator( |
1110 block, use_block); | 1119 block, use_block); |
1111 } | 1120 } |
(...skipping 166 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1278 start->ReplaceInput(NodeProperties::FirstControlIndex(start), block_start); | 1287 start->ReplaceInput(NodeProperties::FirstControlIndex(start), block_start); |
1279 | 1288 |
1280 Trace(" Connecting floating control start %d:%s to %d:%s\n", start->id(), | 1289 Trace(" Connecting floating control start %d:%s to %d:%s\n", start->id(), |
1281 start->op()->mnemonic(), block_start->id(), | 1290 start->op()->mnemonic(), block_start->id(), |
1282 block_start->op()->mnemonic()); | 1291 block_start->op()->mnemonic()); |
1283 } | 1292 } |
1284 | 1293 |
1285 } // namespace compiler | 1294 } // namespace compiler |
1286 } // namespace internal | 1295 } // namespace internal |
1287 } // namespace v8 | 1296 } // namespace v8 |
OLD | NEW |