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 10 matching lines...) Expand all Loading... |
21 static inline void Trace(const char* msg, ...) { | 21 static inline void Trace(const char* msg, ...) { |
22 if (FLAG_trace_turbo_scheduler) { | 22 if (FLAG_trace_turbo_scheduler) { |
23 va_list arguments; | 23 va_list arguments; |
24 va_start(arguments, msg); | 24 va_start(arguments, msg); |
25 base::OS::VPrint(msg, arguments); | 25 base::OS::VPrint(msg, arguments); |
26 va_end(arguments); | 26 va_end(arguments); |
27 } | 27 } |
28 } | 28 } |
29 | 29 |
30 | 30 |
31 Scheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule) | 31 Scheduler::Scheduler(ZonePool* zone_pool, Zone* zone, Graph* graph, |
32 : zone_(zone), | 32 Schedule* schedule) |
| 33 : zone_pool_(zone_pool), |
| 34 zone_(zone), |
33 graph_(graph), | 35 graph_(graph), |
34 schedule_(schedule), | 36 schedule_(schedule), |
35 scheduled_nodes_(zone), | 37 scheduled_nodes_(zone), |
36 schedule_root_nodes_(zone), | 38 schedule_root_nodes_(zone), |
37 node_data_(graph_->NodeCount(), DefaultSchedulerData(), zone), | 39 node_data_(graph_->NodeCount(), DefaultSchedulerData(), zone), |
38 has_floating_control_(false) {} | 40 has_floating_control_(false) {} |
39 | 41 |
40 | 42 |
41 Schedule* Scheduler::ComputeSchedule(Graph* graph) { | 43 Schedule* Scheduler::ComputeSchedule(ZonePool* zone_pool, Graph* graph) { |
42 Schedule* schedule; | 44 Schedule* schedule; |
43 bool had_floating_control = false; | 45 bool had_floating_control = false; |
44 do { | 46 do { |
45 Zone tmp_zone(graph->zone()->isolate()); | 47 ZonePool::Scope zone_scope(zone_pool); |
46 schedule = new (graph->zone()) | 48 schedule = new (graph->zone()) |
47 Schedule(graph->zone(), static_cast<size_t>(graph->NodeCount())); | 49 Schedule(graph->zone(), static_cast<size_t>(graph->NodeCount())); |
48 Scheduler scheduler(&tmp_zone, graph, schedule); | 50 Scheduler scheduler(zone_pool, zone_scope.zone(), graph, schedule); |
49 | 51 |
50 scheduler.BuildCFG(); | 52 scheduler.BuildCFG(); |
51 Scheduler::ComputeSpecialRPO(schedule); | 53 Scheduler::ComputeSpecialRPO(zone_pool, schedule); |
52 scheduler.GenerateImmediateDominatorTree(); | 54 scheduler.GenerateImmediateDominatorTree(); |
53 | 55 |
54 scheduler.PrepareUses(); | 56 scheduler.PrepareUses(); |
55 scheduler.ScheduleEarly(); | 57 scheduler.ScheduleEarly(); |
56 scheduler.ScheduleLate(); | 58 scheduler.ScheduleLate(); |
57 | 59 |
58 had_floating_control = scheduler.ConnectFloatingControl(); | 60 had_floating_control = scheduler.ConnectFloatingControl(); |
59 } while (had_floating_control); | 61 } while (had_floating_control); |
60 | 62 |
61 return schedule; | 63 return schedule; |
(...skipping 603 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
665 i != schedule_root_nodes_.end(); ++i) { | 667 i != schedule_root_nodes_.end(); ++i) { |
666 Trace("#%d:%s ", (*i)->id(), (*i)->op()->mnemonic()); | 668 Trace("#%d:%s ", (*i)->id(), (*i)->op()->mnemonic()); |
667 } | 669 } |
668 Trace("\n"); | 670 Trace("\n"); |
669 } | 671 } |
670 | 672 |
671 // Schedule: Places nodes in dominator block of all their uses. | 673 // Schedule: Places nodes in dominator block of all their uses. |
672 ScheduleLateNodeVisitor schedule_late_visitor(this); | 674 ScheduleLateNodeVisitor schedule_late_visitor(this); |
673 | 675 |
674 { | 676 { |
675 Zone zone(zone_->isolate()); | 677 ZonePool::Scope zone_scope(zone_pool_); |
| 678 Zone* zone = zone_scope.zone(); |
676 GenericGraphVisit::Visit<ScheduleLateNodeVisitor, | 679 GenericGraphVisit::Visit<ScheduleLateNodeVisitor, |
677 NodeInputIterationTraits<Node> >( | 680 NodeInputIterationTraits<Node> >( |
678 graph_, &zone, schedule_root_nodes_.begin(), schedule_root_nodes_.end(), | 681 graph_, zone, schedule_root_nodes_.begin(), schedule_root_nodes_.end(), |
679 &schedule_late_visitor); | 682 &schedule_late_visitor); |
680 } | 683 } |
681 | 684 |
682 // Add collected nodes for basic blocks to their blocks in the right order. | 685 // Add collected nodes for basic blocks to their blocks in the right order. |
683 int block_num = 0; | 686 int block_num = 0; |
684 for (NodeVectorVectorIter i = scheduled_nodes_.begin(); | 687 for (NodeVectorVectorIter i = scheduled_nodes_.begin(); |
685 i != scheduled_nodes_.end(); ++i) { | 688 i != scheduled_nodes_.end(); ++i) { |
686 for (NodeVectorRIter j = i->rbegin(); j != i->rend(); ++j) { | 689 for (NodeVectorRIter j = i->rbegin(); j != i->rend(); ++j) { |
687 schedule_->AddNode(schedule_->all_blocks_.at(block_num), *j); | 690 schedule_->AddNode(schedule_->all_blocks_.at(block_num), *j); |
688 } | 691 } |
(...skipping 303 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
992 // a RPO of the graph where loop bodies are contiguous. Properties: | 995 // a RPO of the graph where loop bodies are contiguous. Properties: |
993 // 1. If block A is a predecessor of B, then A appears before B in the order, | 996 // 1. If block A is a predecessor of B, then A appears before B in the order, |
994 // unless B is a loop header and A is in the loop headed at B | 997 // unless B is a loop header and A is in the loop headed at B |
995 // (i.e. A -> B is a backedge). | 998 // (i.e. A -> B is a backedge). |
996 // => If block A dominates block B, then A appears before B in the order. | 999 // => If block A dominates block B, then A appears before B in the order. |
997 // => If block A is a loop header, A appears before all blocks in the loop | 1000 // => If block A is a loop header, A appears before all blocks in the loop |
998 // headed at A. | 1001 // headed at A. |
999 // 2. All loops are contiguous in the order (i.e. no intervening blocks that | 1002 // 2. All loops are contiguous in the order (i.e. no intervening blocks that |
1000 // do not belong to the loop.) | 1003 // do not belong to the loop.) |
1001 // Note a simple RPO traversal satisfies (1) but not (3). | 1004 // Note a simple RPO traversal satisfies (1) but not (3). |
1002 BasicBlockVector* Scheduler::ComputeSpecialRPO(Schedule* schedule) { | 1005 BasicBlockVector* Scheduler::ComputeSpecialRPO(ZonePool* zone_pool, |
1003 Zone tmp_zone(schedule->zone()->isolate()); | 1006 Schedule* schedule) { |
1004 Zone* zone = &tmp_zone; | 1007 ZonePool::Scope zone_scope(zone_pool); |
| 1008 Zone* zone = zone_scope.zone(); |
1005 Trace("--- COMPUTING SPECIAL RPO ----------------------------------\n"); | 1009 Trace("--- COMPUTING SPECIAL RPO ----------------------------------\n"); |
1006 // RPO should not have been computed for this schedule yet. | 1010 // RPO should not have been computed for this schedule yet. |
1007 CHECK_EQ(kBlockUnvisited1, schedule->start()->rpo_number()); | 1011 CHECK_EQ(kBlockUnvisited1, schedule->start()->rpo_number()); |
1008 CHECK_EQ(0, static_cast<int>(schedule->rpo_order_.size())); | 1012 CHECK_EQ(0, static_cast<int>(schedule->rpo_order_.size())); |
1009 | 1013 |
1010 // Perform an iterative RPO traversal using an explicit stack, | 1014 // Perform an iterative RPO traversal using an explicit stack, |
1011 // recording backedges that form cycles. O(|B|). | 1015 // recording backedges that form cycles. O(|B|). |
1012 ZoneList<std::pair<BasicBlock*, size_t> > backedges(1, zone); | 1016 ZoneList<std::pair<BasicBlock*, size_t> > backedges(1, zone); |
1013 SpecialRPOStackFrame* stack = zone->NewArray<SpecialRPOStackFrame>( | 1017 SpecialRPOStackFrame* stack = zone->NewArray<SpecialRPOStackFrame>( |
1014 static_cast<int>(schedule->BasicBlockCount())); | 1018 static_cast<int>(schedule->BasicBlockCount())); |
(...skipping 174 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1189 #if DEBUG | 1193 #if DEBUG |
1190 if (FLAG_trace_turbo_scheduler) PrintRPO(num_loops, loops, final_order); | 1194 if (FLAG_trace_turbo_scheduler) PrintRPO(num_loops, loops, final_order); |
1191 VerifySpecialRPO(num_loops, loops, final_order); | 1195 VerifySpecialRPO(num_loops, loops, final_order); |
1192 #endif | 1196 #endif |
1193 return final_order; | 1197 return final_order; |
1194 } | 1198 } |
1195 | 1199 |
1196 } // namespace compiler | 1200 } // namespace compiler |
1197 } // namespace internal | 1201 } // namespace internal |
1198 } // namespace v8 | 1202 } // namespace v8 |
OLD | NEW |