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/base/flags.h" |
10 #include "src/compiler/node.h" | 11 #include "src/compiler/node.h" |
11 #include "src/compiler/opcodes.h" | 12 #include "src/compiler/opcodes.h" |
12 #include "src/compiler/schedule.h" | 13 #include "src/compiler/schedule.h" |
13 #include "src/compiler/zone-pool.h" | 14 #include "src/compiler/zone-pool.h" |
14 #include "src/zone-containers.h" | 15 #include "src/zone-containers.h" |
15 | 16 |
16 namespace v8 { | 17 namespace v8 { |
17 namespace internal { | 18 namespace internal { |
18 namespace compiler { | 19 namespace compiler { |
19 | 20 |
20 // Forward declarations. | 21 // Forward declarations. |
21 class CFGBuilder; | 22 class CFGBuilder; |
22 class ControlEquivalence; | 23 class ControlEquivalence; |
23 class Graph; | 24 class Graph; |
24 class SpecialRPONumberer; | 25 class SpecialRPONumberer; |
25 | 26 |
26 | 27 |
27 // Computes a schedule from a graph, placing nodes into basic blocks and | 28 // Computes a schedule from a graph, placing nodes into basic blocks and |
28 // ordering the basic blocks in the special RPO order. | 29 // ordering the basic blocks in the special RPO order. |
29 class Scheduler { | 30 class Scheduler { |
30 public: | 31 public: |
| 32 // Flags that control the mode of operation. |
| 33 enum Flag { kNoFlags = 0u, kSplitNodes = 1u << 1 }; |
| 34 typedef base::Flags<Flag> Flags; |
| 35 |
31 // The complete scheduling algorithm. Creates a new schedule and places all | 36 // The complete scheduling algorithm. Creates a new schedule and places all |
32 // nodes from the graph into it. | 37 // nodes from the graph into it. |
33 static Schedule* ComputeSchedule(Zone* zone, Graph* graph); | 38 static Schedule* ComputeSchedule(Zone* zone, Graph* graph, Flags flags); |
34 | 39 |
35 // Compute the RPO of blocks in an existing schedule. | 40 // Compute the RPO of blocks in an existing schedule. |
36 static BasicBlockVector* ComputeSpecialRPO(Zone* zone, Schedule* schedule); | 41 static BasicBlockVector* ComputeSpecialRPO(Zone* zone, Schedule* schedule); |
37 | 42 |
38 private: | 43 private: |
39 // Placement of a node changes during scheduling. The placement state | 44 // Placement of a node changes during scheduling. The placement state |
40 // transitions over time while the scheduler is choosing a position: | 45 // transitions over time while the scheduler is choosing a position: |
41 // | 46 // |
42 // +---------------------+-----+----> kFixed | 47 // +---------------------+-----+----> kFixed |
43 // / / / | 48 // / / / |
44 // kUnknown ----+------> kCoupled ----+ / | 49 // kUnknown ----+------> kCoupled ----+ / |
45 // \ / | 50 // \ / |
46 // +----> kSchedulable ----+--------> kScheduled | 51 // +----> kSchedulable ----+--------> kScheduled |
47 // | 52 // |
48 // 1) GetPlacement(): kUnknown -> kCoupled|kSchedulable|kFixed | 53 // 1) GetPlacement(): kUnknown -> kCoupled|kSchedulable|kFixed |
49 // 2) UpdatePlacement(): kCoupled|kSchedulable -> kFixed|kScheduled | 54 // 2) UpdatePlacement(): kCoupled|kSchedulable -> kFixed|kScheduled |
50 enum Placement { kUnknown, kSchedulable, kFixed, kCoupled, kScheduled }; | 55 enum Placement { kUnknown, kSchedulable, kFixed, kCoupled, kScheduled }; |
51 | 56 |
52 // Per-node data tracked during scheduling. | 57 // Per-node data tracked during scheduling. |
53 struct SchedulerData { | 58 struct SchedulerData { |
54 BasicBlock* minimum_block_; // Minimum legal RPO placement. | 59 BasicBlock* minimum_block_; // Minimum legal RPO placement. |
55 int unscheduled_count_; // Number of unscheduled uses of this node. | 60 int unscheduled_count_; // Number of unscheduled uses of this node. |
56 Placement placement_; // Whether the node is fixed, schedulable, | 61 Placement placement_; // Whether the node is fixed, schedulable, |
57 // coupled to another node, or not yet known. | 62 // coupled to another node, or not yet known. |
58 }; | 63 }; |
59 | 64 |
60 Zone* zone_; | 65 Zone* zone_; |
61 Graph* graph_; | 66 Graph* graph_; |
62 Schedule* schedule_; | 67 Schedule* schedule_; |
| 68 Flags flags_; |
63 NodeVectorVector scheduled_nodes_; // Per-block list of nodes in reverse. | 69 NodeVectorVector scheduled_nodes_; // Per-block list of nodes in reverse. |
64 NodeVector schedule_root_nodes_; // Fixed root nodes seed the worklist. | 70 NodeVector schedule_root_nodes_; // Fixed root nodes seed the worklist. |
65 ZoneQueue<Node*> schedule_queue_; // Worklist of schedulable nodes. | 71 ZoneQueue<Node*> schedule_queue_; // Worklist of schedulable nodes. |
66 ZoneVector<SchedulerData> node_data_; // Per-node data for all nodes. | 72 ZoneVector<SchedulerData> node_data_; // Per-node data for all nodes. |
67 CFGBuilder* control_flow_builder_; // Builds basic blocks for controls. | 73 CFGBuilder* control_flow_builder_; // Builds basic blocks for controls. |
68 SpecialRPONumberer* special_rpo_; // Special RPO numbering of blocks. | 74 SpecialRPONumberer* special_rpo_; // Special RPO numbering of blocks. |
69 ControlEquivalence* equivalence_; // Control dependence equivalence. | 75 ControlEquivalence* equivalence_; // Control dependence equivalence. |
70 | 76 |
71 Scheduler(Zone* zone, Graph* graph, Schedule* schedule); | 77 Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags); |
72 | 78 |
73 inline SchedulerData DefaultSchedulerData(); | 79 inline SchedulerData DefaultSchedulerData(); |
74 inline SchedulerData* GetData(Node* node); | 80 inline SchedulerData* GetData(Node* node); |
75 | 81 |
76 Placement GetPlacement(Node* node); | 82 Placement GetPlacement(Node* node); |
77 void UpdatePlacement(Node* node, Placement placement); | 83 void UpdatePlacement(Node* node, Placement placement); |
78 | 84 |
79 inline bool IsCoupledControlEdge(Node* node, int index); | 85 inline bool IsCoupledControlEdge(Node* node, int index); |
80 void IncrementUnscheduledUseCount(Node* node, int index, Node* from); | 86 void IncrementUnscheduledUseCount(Node* node, int index, Node* from); |
81 void DecrementUnscheduledUseCount(Node* node, int index, Node* from); | 87 void DecrementUnscheduledUseCount(Node* node, int index, Node* from); |
(...skipping 21 matching lines...) Expand all Loading... |
103 friend class ScheduleLateNodeVisitor; | 109 friend class ScheduleLateNodeVisitor; |
104 void ScheduleLate(); | 110 void ScheduleLate(); |
105 | 111 |
106 // Phase 6: Seal the final schedule. | 112 // Phase 6: Seal the final schedule. |
107 void SealFinalSchedule(); | 113 void SealFinalSchedule(); |
108 | 114 |
109 void FuseFloatingControl(BasicBlock* block, Node* node); | 115 void FuseFloatingControl(BasicBlock* block, Node* node); |
110 void MovePlannedNodes(BasicBlock* from, BasicBlock* to); | 116 void MovePlannedNodes(BasicBlock* from, BasicBlock* to); |
111 }; | 117 }; |
112 | 118 |
| 119 |
| 120 DEFINE_OPERATORS_FOR_FLAGS(Scheduler::Flags) |
| 121 |
113 } // namespace compiler | 122 } // namespace compiler |
114 } // namespace internal | 123 } // namespace internal |
115 } // namespace v8 | 124 } // namespace v8 |
116 | 125 |
117 #endif // V8_COMPILER_SCHEDULER_H_ | 126 #endif // V8_COMPILER_SCHEDULER_H_ |
OLD | NEW |