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 #ifndef V8_COMPILER_SCHEDULER_H_ | 5 #ifndef V8_COMPILER_SCHEDULER_H_ |
6 #define V8_COMPILER_SCHEDULER_H_ | 6 #define V8_COMPILER_SCHEDULER_H_ |
7 | 7 |
8 #include "src/v8.h" | 8 #include "src/v8.h" |
9 | 9 |
10 #include "src/compiler/opcodes.h" | 10 #include "src/compiler/opcodes.h" |
11 #include "src/compiler/schedule.h" | 11 #include "src/compiler/schedule.h" |
12 #include "src/zone-containers.h" | 12 #include "src/zone-containers.h" |
13 | 13 |
14 namespace v8 { | 14 namespace v8 { |
15 namespace internal { | 15 namespace internal { |
16 namespace compiler { | 16 namespace compiler { |
17 | 17 |
18 // Computes a schedule from a graph, placing nodes into basic blocks and | 18 // Computes a schedule from a graph, placing nodes into basic blocks and |
19 // ordering the basic blocks in the special RPO order. | 19 // ordering the basic blocks in the special RPO order. |
20 class Scheduler { | 20 class Scheduler { |
21 public: | 21 public: |
22 // The complete scheduling algorithm. | 22 // The complete scheduling algorithm. Creates a new schedule and places all |
23 // Create a new schedule and place all nodes from the graph into it. | 23 // nodes from the graph into it. |
24 static Schedule* ComputeSchedule(Graph* graph); | 24 static Schedule* ComputeSchedule(Graph* graph); |
25 | 25 |
26 // Compute the RPO of blocks in an existing schedule. | 26 // Compute the RPO of blocks in an existing schedule. |
27 static BasicBlockVector* ComputeSpecialRPO(Schedule* schedule); | 27 static BasicBlockVector* ComputeSpecialRPO(Schedule* schedule); |
28 | 28 |
29 // (Exposed for testing only) | |
30 // Build and connect the CFG for a node graph, but don't schedule nodes. | |
31 static void ComputeCFG(Graph* graph, Schedule* schedule); | |
32 | |
33 private: | 29 private: |
34 enum Placement { kUnknown, kSchedulable, kFixed }; | 30 enum Placement { kUnknown, kSchedulable, kFixed }; |
35 | 31 |
36 // Per-node data tracked during scheduling. | 32 // Per-node data tracked during scheduling. |
37 struct SchedulerData { | 33 struct SchedulerData { |
38 int unscheduled_count_; // Number of unscheduled uses of this node. | 34 int unscheduled_count_; // Number of unscheduled uses of this node. |
39 int minimum_rpo_; // Minimum legal RPO placement. | 35 int minimum_rpo_; // Minimum legal RPO placement. |
40 bool is_connected_control_; // {true} if control-connected to the end node. | 36 bool is_connected_control_; // {true} if control-connected to the end node. |
41 bool is_floating_control_; // {true} if control, but not control-connected | 37 bool is_floating_control_; // {true} if control, but not control-connected |
42 // to the end node. | 38 // to the end node. |
(...skipping 11 matching lines...) Expand all Loading... |
54 | 50 |
55 Scheduler(Zone* zone, Graph* graph, Schedule* schedule); | 51 Scheduler(Zone* zone, Graph* graph, Schedule* schedule); |
56 | 52 |
57 SchedulerData DefaultSchedulerData(); | 53 SchedulerData DefaultSchedulerData(); |
58 | 54 |
59 SchedulerData* GetData(Node* node) { | 55 SchedulerData* GetData(Node* node) { |
60 DCHECK(node->id() < static_cast<int>(node_data_.size())); | 56 DCHECK(node->id() < static_cast<int>(node_data_.size())); |
61 return &node_data_[node->id()]; | 57 return &node_data_[node->id()]; |
62 } | 58 } |
63 | 59 |
64 void BuildCFG(); | |
65 | |
66 Placement GetPlacement(Node* node); | 60 Placement GetPlacement(Node* node); |
67 | 61 |
68 int GetRPONumber(BasicBlock* block) { | 62 int GetRPONumber(BasicBlock* block) { |
69 DCHECK(block->rpo_number() >= 0 && | 63 DCHECK(block->rpo_number() >= 0 && |
70 block->rpo_number() < | 64 block->rpo_number() < |
71 static_cast<int>(schedule_->rpo_order_.size())); | 65 static_cast<int>(schedule_->rpo_order_.size())); |
72 DCHECK(schedule_->rpo_order_[block->rpo_number()] == block); | 66 DCHECK(schedule_->rpo_order_[block->rpo_number()] == block); |
73 return block->rpo_number(); | 67 return block->rpo_number(); |
74 } | 68 } |
75 | 69 |
76 void GenerateImmediateDominatorTree(); | |
77 BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2); | 70 BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2); |
78 | 71 |
| 72 // Phase 1: Build control-flow graph and dominator tree. |
79 friend class CFGBuilder; | 73 friend class CFGBuilder; |
| 74 void BuildCFG(); |
| 75 void GenerateImmediateDominatorTree(); |
80 | 76 |
| 77 // Phase 2: Prepare use counts for nodes. |
| 78 friend class PrepareUsesVisitor; |
| 79 void PrepareUses(); |
| 80 |
| 81 // Phase 3: Schedule nodes early. |
81 friend class ScheduleEarlyNodeVisitor; | 82 friend class ScheduleEarlyNodeVisitor; |
82 void ScheduleEarly(); | 83 void ScheduleEarly(); |
83 | 84 |
84 friend class PrepareUsesVisitor; | 85 // Phase 4: Schedule nodes late. |
85 void PrepareUses(); | |
86 | |
87 friend class ScheduleLateNodeVisitor; | 86 friend class ScheduleLateNodeVisitor; |
88 void ScheduleLate(); | 87 void ScheduleLate(); |
89 | 88 |
90 bool ConnectFloatingControl(); | 89 bool ConnectFloatingControl(); |
91 | |
92 void ConnectFloatingControlSubgraph(BasicBlock* block, Node* node); | 90 void ConnectFloatingControlSubgraph(BasicBlock* block, Node* node); |
93 }; | 91 }; |
94 } | 92 |
95 } | 93 } // namespace compiler |
96 } // namespace v8::internal::compiler | 94 } // namespace internal |
| 95 } // namespace v8 |
97 | 96 |
98 #endif // V8_COMPILER_SCHEDULER_H_ | 97 #endif // V8_COMPILER_SCHEDULER_H_ |
OLD | NEW |