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
16namespace v8 {
17namespace internal {
18namespace compiler {
19
20// Forward declarations.
21class CFGBuilder;
22class ControlEquivalence;
23class Graph;
24class 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.
29class V8_EXPORT_PRIVATE Scheduler {
30 public:
31  // Flags that control the mode of operation.
32  enum Flag { kNoFlags = 0u, kSplitNodes = 1u << 1 };
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* 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) GetPlacement(): kUnknown -> kCoupled|kSchedulable|kFixed
53  // 2) UpdatePlacement(): kCoupled|kSchedulable -> kFixed|kScheduled
54  enum Placement { kUnknown, kSchedulable, kFixed, kCoupled, kScheduled };
55
56  // Per-node data tracked during scheduling.
57  struct SchedulerData {
58    BasicBlock* minimum_block_;  // Minimum legal RPO placement.
59    int unscheduled_count_;      // Number of unscheduled uses of this node.
60    Placement placement_;        // Whether the node is fixed, schedulable,
61                                 // coupled to another node, or not yet known.
62  };
63
64  Zone* zone_;
65  Graph* graph_;
66  Schedule* schedule_;
67  Flags flags_;
68  NodeVectorVector scheduled_nodes_;     // Per-block list of nodes in reverse.
69  NodeVector schedule_root_nodes_;       // Fixed root nodes seed the worklist.
70  ZoneQueue<Node*> schedule_queue_;      // Worklist of schedulable nodes.
71  ZoneVector<SchedulerData> node_data_;  // Per-node data for all nodes.
72  CFGBuilder* control_flow_builder_;     // Builds basic blocks for controls.
73  SpecialRPONumberer* special_rpo_;      // Special RPO numbering of blocks.
74  ControlEquivalence* equivalence_;      // Control dependence equivalence.
75
76  Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags);
77
78  inline SchedulerData DefaultSchedulerData();
79  inline SchedulerData* GetData(Node* node);
80
81  Placement GetPlacement(Node* node);
82  void UpdatePlacement(Node* node, Placement placement);
83
84  inline bool IsCoupledControlEdge(Node* node, int index);
85  void IncrementUnscheduledUseCount(Node* node, int index, Node* from);
86  void DecrementUnscheduledUseCount(Node* node, int index, Node* from);
87
88  void PropagateImmediateDominators(BasicBlock* block);
89
90  // Phase 1: Build control-flow graph.
91  friend class CFGBuilder;
92  void BuildCFG();
93
94  // Phase 2: Compute special RPO and dominator tree.
95  friend class SpecialRPONumberer;
96  void ComputeSpecialRPONumbering();
97  void GenerateImmediateDominatorTree();
98
99  // Phase 3: Prepare use counts for nodes.
100  friend class PrepareUsesVisitor;
101  void PrepareUses();
102
103  // Phase 4: Schedule nodes early.
104  friend class ScheduleEarlyNodeVisitor;
105  void ScheduleEarly();
106
107  // Phase 5: Schedule nodes late.
108  friend class ScheduleLateNodeVisitor;
109  void ScheduleLate();
110
111  // Phase 6: Seal the final schedule.
112  void SealFinalSchedule();
113
114  void FuseFloatingControl(BasicBlock* block, Node* node);
115  void MovePlannedNodes(BasicBlock* from, BasicBlock* to);
116};
117
118
119DEFINE_OPERATORS_FOR_FLAGS(Scheduler::Flags)
120
121}  // namespace compiler
122}  // namespace internal
123}  // namespace v8
124
125#endif  // V8_COMPILER_SCHEDULER_H_
126