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