Line data Source code
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
3 : // found in the LICENSE file.
4 :
5 : #ifndef V8_COMPILER_SCHEDULER_H_
6 : #define V8_COMPILER_SCHEDULER_H_
7 :
8 : #include "src/base/flags.h"
9 : #include "src/compiler/node.h"
10 : #include "src/compiler/opcodes.h"
11 : #include "src/compiler/schedule.h"
12 : #include "src/compiler/zone-stats.h"
13 : #include "src/globals.h"
14 : #include "src/zone/zone-containers.h"
15 :
16 : namespace v8 {
17 : namespace internal {
18 : namespace compiler {
19 :
20 : // Forward declarations.
21 : class CFGBuilder;
22 : class ControlEquivalence;
23 : class Graph;
24 : class SpecialRPONumberer;
25 :
26 :
27 : // Computes a schedule from a graph, placing nodes into basic blocks and
28 : // ordering the basic blocks in the special RPO order.
29 2869195 : class V8_EXPORT_PRIVATE Scheduler {
30 : public:
31 : // Flags that control the mode of operation.
32 : enum Flag { kNoFlags = 0u, kSplitNodes = 1u << 1, kTempSchedule = 1u << 2 };
33 : using Flags = base::Flags<Flag>;
34 :
35 : // The complete scheduling algorithm. Creates a new schedule and places all
36 : // nodes from the graph into it.
37 : static Schedule* ComputeSchedule(Zone* temp_zone, Graph* graph, Flags flags);
38 :
39 : // Compute the RPO of blocks in an existing schedule.
40 : static BasicBlockVector* ComputeSpecialRPO(Zone* zone, Schedule* schedule);
41 :
42 : private:
43 : // Placement of a node changes during scheduling. The placement state
44 : // transitions over time while the scheduler is choosing a position:
45 : //
46 : // +---------------------+-----+----> kFixed
47 : // / / /
48 : // kUnknown ----+------> kCoupled ----+ /
49 : // \ /
50 : // +----> kSchedulable ----+--------> kScheduled
51 : //
52 : // 1) InitializePlacement(): kUnknown -> kCoupled|kSchedulable|kFixed
53 : // 2) UpdatePlacement(): kCoupled|kSchedulable -> kFixed|kScheduled
54 : //
55 : // We maintain the invariant that all nodes that are not reachable
56 : // from the end have kUnknown placement. After the PrepareUses phase runs,
57 : // also the opposite is true - all nodes with kUnknown placement are not
58 : // reachable from the end.
59 : enum Placement { kUnknown, kSchedulable, kFixed, kCoupled, kScheduled };
60 :
61 : // Per-node data tracked during scheduling.
62 : struct SchedulerData {
63 : BasicBlock* minimum_block_; // Minimum legal RPO placement.
64 : int unscheduled_count_; // Number of unscheduled uses of this node.
65 : Placement placement_; // Whether the node is fixed, schedulable,
66 : // coupled to another node, or not yet known.
67 : };
68 :
69 : Zone* zone_;
70 : Graph* graph_;
71 : Schedule* schedule_;
72 : Flags flags_;
73 : ZoneVector<NodeVector*>
74 : scheduled_nodes_; // Per-block list of nodes in reverse.
75 : NodeVector schedule_root_nodes_; // Fixed root nodes seed the worklist.
76 : ZoneQueue<Node*> schedule_queue_; // Worklist of schedulable nodes.
77 : ZoneVector<SchedulerData> node_data_; // Per-node data for all nodes.
78 : CFGBuilder* control_flow_builder_; // Builds basic blocks for controls.
79 : SpecialRPONumberer* special_rpo_; // Special RPO numbering of blocks.
80 : ControlEquivalence* equivalence_; // Control dependence equivalence.
81 :
82 : Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags,
83 : size_t node_count_hint_);
84 :
85 : inline SchedulerData DefaultSchedulerData();
86 : inline SchedulerData* GetData(Node* node);
87 :
88 : Placement GetPlacement(Node* node);
89 : Placement InitializePlacement(Node* node);
90 : void UpdatePlacement(Node* node, Placement placement);
91 : bool IsLive(Node* node);
92 :
93 : inline bool IsCoupledControlEdge(Node* node, int index);
94 : void IncrementUnscheduledUseCount(Node* node, int index, Node* from);
95 : void DecrementUnscheduledUseCount(Node* node, int index, Node* from);
96 :
97 : void PropagateImmediateDominators(BasicBlock* block);
98 :
99 : // Phase 1: Build control-flow graph.
100 : friend class CFGBuilder;
101 : void BuildCFG();
102 :
103 : // Phase 2: Compute special RPO and dominator tree.
104 : friend class SpecialRPONumberer;
105 : void ComputeSpecialRPONumbering();
106 : void GenerateImmediateDominatorTree();
107 :
108 : // Phase 3: Prepare use counts for nodes.
109 : friend class PrepareUsesVisitor;
110 : void PrepareUses();
111 :
112 : // Phase 4: Schedule nodes early.
113 : friend class ScheduleEarlyNodeVisitor;
114 : void ScheduleEarly();
115 :
116 : // Phase 5: Schedule nodes late.
117 : friend class ScheduleLateNodeVisitor;
118 : void ScheduleLate();
119 :
120 : // Phase 6: Seal the final schedule.
121 : void SealFinalSchedule();
122 :
123 : void FuseFloatingControl(BasicBlock* block, Node* node);
124 : void MovePlannedNodes(BasicBlock* from, BasicBlock* to);
125 : };
126 :
127 :
128 : DEFINE_OPERATORS_FOR_FLAGS(Scheduler::Flags)
129 :
130 : } // namespace compiler
131 : } // namespace internal
132 : } // namespace v8
133 :
134 : #endif // V8_COMPILER_SCHEDULER_H_
|