| 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 |