V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
scheduler.h
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 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  typedef base::Flags<Flag> Flags;
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_;
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_
Definition: libplatform.h:13