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. Creates a new schedule and places all | 22 // The complete scheduling algorithm. Creates a new schedule and places all |
23 // 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 private: | 29 private: |
30 enum Placement { kUnknown, kSchedulable, kFixed }; | 30 enum Placement { kUnknown, kSchedulable, kFixed, kCoupled }; |
31 | 31 |
32 // Per-node data tracked during scheduling. | 32 // Per-node data tracked during scheduling. |
33 struct SchedulerData { | 33 struct SchedulerData { |
34 BasicBlock* minimum_block_; // Minimum legal RPO placement. | 34 BasicBlock* minimum_block_; // Minimum legal RPO placement. |
35 int unscheduled_count_; // Number of unscheduled uses of this node. | 35 int unscheduled_count_; // Number of unscheduled uses of this node. |
36 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. |
37 bool is_floating_control_; // {true} if control, but not control-connected | 37 bool is_floating_control_; // {true} if control, but not control-connected |
38 // to the end node. | 38 // to the end node. |
39 Placement placement_ : 3; // Whether the node is fixed, schedulable, | 39 Placement placement_ : 2; // Whether the node is fixed, schedulable, |
40 // or not yet known. | 40 // coupled to another node, or not yet known. |
41 }; | 41 }; |
42 | 42 |
43 Zone* zone_; | 43 Zone* zone_; |
44 Graph* graph_; | 44 Graph* graph_; |
45 Schedule* schedule_; | 45 Schedule* schedule_; |
46 NodeVectorVector scheduled_nodes_; | 46 NodeVectorVector scheduled_nodes_; |
47 NodeVector schedule_root_nodes_; | 47 NodeVector schedule_root_nodes_; |
48 ZoneVector<SchedulerData> node_data_; | 48 ZoneVector<SchedulerData> node_data_; |
49 bool has_floating_control_; | 49 bool has_floating_control_; |
50 | 50 |
51 Scheduler(Zone* zone, Graph* graph, Schedule* schedule); | 51 Scheduler(Zone* zone, Graph* graph, Schedule* schedule); |
52 | 52 |
53 SchedulerData DefaultSchedulerData(); | 53 inline SchedulerData DefaultSchedulerData(); |
54 | 54 inline SchedulerData* GetData(Node* node); |
55 SchedulerData* GetData(Node* node) { | |
56 DCHECK(node->id() < static_cast<int>(node_data_.size())); | |
57 return &node_data_[node->id()]; | |
58 } | |
59 | 55 |
60 Placement GetPlacement(Node* node); | 56 Placement GetPlacement(Node* node); |
61 | 57 |
62 int GetRPONumber(BasicBlock* block) { | 58 void IncrementUnscheduledUseCount(Node* node, Node* from); |
63 DCHECK(block->rpo_number() >= 0 && | 59 void DecrementUnscheduledUseCount(Node* node, Node* from); |
64 block->rpo_number() < | |
65 static_cast<int>(schedule_->rpo_order_.size())); | |
66 DCHECK(schedule_->rpo_order_[block->rpo_number()] == block); | |
67 return block->rpo_number(); | |
68 } | |
69 | 60 |
| 61 inline int GetRPONumber(BasicBlock* block); |
70 BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2); | 62 BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2); |
71 | 63 |
72 // Phase 1: Build control-flow graph and dominator tree. | 64 // Phase 1: Build control-flow graph and dominator tree. |
73 friend class CFGBuilder; | 65 friend class CFGBuilder; |
74 void BuildCFG(); | 66 void BuildCFG(); |
75 void GenerateImmediateDominatorTree(); | 67 void GenerateImmediateDominatorTree(); |
76 | 68 |
77 // Phase 2: Prepare use counts for nodes. | 69 // Phase 2: Prepare use counts for nodes. |
78 friend class PrepareUsesVisitor; | 70 friend class PrepareUsesVisitor; |
79 void PrepareUses(); | 71 void PrepareUses(); |
80 | 72 |
81 // Phase 3: Schedule nodes early. | 73 // Phase 3: Schedule nodes early. |
82 friend class ScheduleEarlyNodeVisitor; | 74 friend class ScheduleEarlyNodeVisitor; |
83 void ScheduleEarly(); | 75 void ScheduleEarly(); |
84 | 76 |
85 // Phase 4: Schedule nodes late. | 77 // Phase 4: Schedule nodes late. |
86 friend class ScheduleLateNodeVisitor; | 78 friend class ScheduleLateNodeVisitor; |
87 void ScheduleLate(); | 79 void ScheduleLate(); |
88 | 80 |
89 bool ConnectFloatingControl(); | 81 bool ConnectFloatingControl(); |
90 void ConnectFloatingControlSubgraph(BasicBlock* block, Node* node); | 82 void ConnectFloatingControlSubgraph(BasicBlock* block, Node* node); |
91 }; | 83 }; |
92 | 84 |
93 } // namespace compiler | 85 } // namespace compiler |
94 } // namespace internal | 86 } // namespace internal |
95 } // namespace v8 | 87 } // namespace v8 |
96 | 88 |
97 #endif // V8_COMPILER_SCHEDULER_H_ | 89 #endif // V8_COMPILER_SCHEDULER_H_ |
OLD | NEW |