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" |
(...skipping 11 matching lines...) Expand all Loading... |
22 public: | 22 public: |
23 // The complete scheduling algorithm. Creates a new schedule and places all | 23 // The complete scheduling algorithm. Creates a new schedule and places all |
24 // nodes from the graph into it. | 24 // nodes from the graph into it. |
25 static Schedule* ComputeSchedule(ZonePool* zone_pool, Graph* graph); | 25 static Schedule* ComputeSchedule(ZonePool* zone_pool, Graph* graph); |
26 | 26 |
27 // Compute the RPO of blocks in an existing schedule. | 27 // Compute the RPO of blocks in an existing schedule. |
28 static BasicBlockVector* ComputeSpecialRPO(ZonePool* zone_pool, | 28 static BasicBlockVector* ComputeSpecialRPO(ZonePool* zone_pool, |
29 Schedule* schedule); | 29 Schedule* schedule); |
30 | 30 |
31 private: | 31 private: |
32 enum Placement { kUnknown, kSchedulable, kFixed, kCoupled }; | 32 // Placement of a node changes during scheduling. The placement state |
| 33 // transitions over time while the scheduler is choosing a position: |
| 34 // |
| 35 // +---------------------+-----+----> kFixed |
| 36 // / / / |
| 37 // kUnknown ----+------> kCoupled ----+ / |
| 38 // \ / |
| 39 // +----> kSchedulable ----+--------> kScheduled |
| 40 // |
| 41 // 1) GetPlacement(): kUnknown -> kCoupled|kSchedulable|kFixed |
| 42 // 2) UpdatePlacement(): kCoupled|kSchedulable -> kFixed|kScheduled |
| 43 enum Placement { kUnknown, kSchedulable, kFixed, kCoupled, kScheduled }; |
33 | 44 |
34 // Per-node data tracked during scheduling. | 45 // Per-node data tracked during scheduling. |
35 struct SchedulerData { | 46 struct SchedulerData { |
36 BasicBlock* minimum_block_; // Minimum legal RPO placement. | 47 BasicBlock* minimum_block_; // Minimum legal RPO placement. |
37 int unscheduled_count_; // Number of unscheduled uses of this node. | 48 int unscheduled_count_; // Number of unscheduled uses of this node. |
38 bool is_connected_control_; // {true} if control-connected to the end node. | 49 bool is_connected_control_; // {true} if control-connected to the end node. |
39 bool is_floating_control_; // {true} if control, but not control-connected | 50 bool is_floating_control_; // {true} if control, but not control-connected |
40 // to the end node. | 51 // to the end node. |
41 Placement placement_; // Whether the node is fixed, schedulable, | 52 Placement placement_; // Whether the node is fixed, schedulable, |
42 // coupled to another node, or not yet known. | 53 // coupled to another node, or not yet known. |
43 }; | 54 }; |
44 | 55 |
45 Zone* zone_; | 56 Zone* zone_; |
46 Graph* graph_; | 57 Graph* graph_; |
47 Schedule* schedule_; | 58 Schedule* schedule_; |
48 NodeVectorVector scheduled_nodes_; // Per-block list of nodes in reverse. | 59 NodeVectorVector scheduled_nodes_; // Per-block list of nodes in reverse. |
49 NodeVector schedule_root_nodes_; // Fixed root nodes seed the worklist. | 60 NodeVector schedule_root_nodes_; // Fixed root nodes seed the worklist. |
50 ZoneQueue<Node*> schedule_queue_; // Worklist of schedulable nodes. | 61 ZoneQueue<Node*> schedule_queue_; // Worklist of schedulable nodes. |
51 ZoneVector<SchedulerData> node_data_; // Per-node data for all nodes. | 62 ZoneVector<SchedulerData> node_data_; // Per-node data for all nodes. |
52 bool has_floating_control_; | |
53 | 63 |
54 Scheduler(Zone* zone, Graph* graph, Schedule* schedule); | 64 Scheduler(Zone* zone, Graph* graph, Schedule* schedule); |
55 | 65 |
56 inline SchedulerData DefaultSchedulerData(); | 66 inline SchedulerData DefaultSchedulerData(); |
57 inline SchedulerData* GetData(Node* node); | 67 inline SchedulerData* GetData(Node* node); |
58 | 68 |
59 Placement GetPlacement(Node* node); | 69 Placement GetPlacement(Node* node); |
| 70 void UpdatePlacement(Node* node, Placement placement); |
60 | 71 |
61 void IncrementUnscheduledUseCount(Node* node, Node* from); | 72 void IncrementUnscheduledUseCount(Node* node, Node* from); |
62 void DecrementUnscheduledUseCount(Node* node, Node* from); | 73 void DecrementUnscheduledUseCount(Node* node, Node* from); |
63 | 74 |
64 inline int GetRPONumber(BasicBlock* block); | 75 inline int GetRPONumber(BasicBlock* block); |
65 BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2); | 76 BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2); |
66 | 77 |
67 // Phase 1: Build control-flow graph. | 78 // Phase 1: Build control-flow graph. |
68 friend class CFGBuilder; | 79 friend class CFGBuilder; |
69 void BuildCFG(); | 80 void BuildCFG(); |
70 | 81 |
71 // Phase 2: Compute special RPO and dominator tree. | 82 // Phase 2: Compute special RPO and dominator tree. |
72 friend class SpecialRPONumberer; | 83 friend class SpecialRPONumberer; |
73 void ComputeSpecialRPONumbering(); | 84 void ComputeSpecialRPONumbering(); |
74 void GenerateImmediateDominatorTree(); | 85 void GenerateImmediateDominatorTree(); |
75 | 86 |
76 // Phase 3: Prepare use counts for nodes. | 87 // Phase 3: Prepare use counts for nodes. |
77 friend class PrepareUsesVisitor; | 88 friend class PrepareUsesVisitor; |
78 void PrepareUses(); | 89 void PrepareUses(); |
79 | 90 |
80 // Phase 4: Schedule nodes early. | 91 // Phase 4: Schedule nodes early. |
81 friend class ScheduleEarlyNodeVisitor; | 92 friend class ScheduleEarlyNodeVisitor; |
82 void ScheduleEarly(); | 93 void ScheduleEarly(); |
83 | 94 |
84 // Phase 5: Schedule nodes late. | 95 // Phase 5: Schedule nodes late. |
85 friend class ScheduleLateNodeVisitor; | 96 friend class ScheduleLateNodeVisitor; |
86 void ScheduleLate(); | 97 void ScheduleLate(); |
87 | 98 |
88 bool ConnectFloatingControl(); | 99 void FuseFloatingControl(BasicBlock* block, Node* node); |
89 void ConnectFloatingControlSubgraph(BasicBlock* block, Node* node); | 100 void MovePlannedNodes(BasicBlock* from, BasicBlock* to); |
90 }; | 101 }; |
91 | 102 |
92 } // namespace compiler | 103 } // namespace compiler |
93 } // namespace internal | 104 } // namespace internal |
94 } // namespace v8 | 105 } // namespace v8 |
95 | 106 |
96 #endif // V8_COMPILER_SCHEDULER_H_ | 107 #endif // V8_COMPILER_SCHEDULER_H_ |
OLD | NEW |