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