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
16namespace v8 {
17namespace internal {
18
19class ProfileDataFromFile;
20class TickCounter;
21
22namespace compiler {
23
24// Forward declarations.
25class CFGBuilder;
26class ControlEquivalence;
27class Graph;
28class 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.
32class 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
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  // Implements a two-dimensional map: (int, int) -> BasicBlock*.
72  using CommonDominatorCache = ZoneMap<int, ZoneMap<int, BasicBlock*>*>;
73
74  // Per-node data tracked during scheduling.
75  struct SchedulerData {
76    BasicBlock* minimum_block_;  // Minimum legal RPO placement.
77    int unscheduled_count_;      // Number of unscheduled uses of this node.
78    Placement placement_;        // Whether the node is fixed, schedulable,
79                                 // coupled to another node, or not yet known.
80  };
81
82  Zone* zone_;
83  Graph* graph_;
84  Schedule* schedule_;
85  Flags flags_;
86  ZoneVector<NodeVector*>
87      scheduled_nodes_;                  // Per-block list of nodes in reverse.
88  NodeVector schedule_root_nodes_;       // Fixed root nodes seed the worklist.
89  ZoneQueue<Node*> schedule_queue_;      // Worklist of schedulable nodes.
90  ZoneVector<SchedulerData> node_data_;  // Per-node data for all nodes.
91  CFGBuilder* control_flow_builder_;     // Builds basic blocks for controls.
92  SpecialRPONumberer* special_rpo_;      // Special RPO numbering of blocks.
93  ControlEquivalence* equivalence_;      // Control dependence equivalence.
94  TickCounter* const tick_counter_;
95  const ProfileDataFromFile* profile_data_;
96  CommonDominatorCache common_dominator_cache_;
97
98  Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags,
99            size_t node_count_hint_, TickCounter* tick_counter,
100            const ProfileDataFromFile* profile_data);
101
102  inline SchedulerData DefaultSchedulerData();
103  inline SchedulerData* GetData(Node* node);
104
105  Placement GetPlacement(Node* node);
106  Placement InitializePlacement(Node* node);
107  void UpdatePlacement(Node* node, Placement placement);
108  bool IsLive(Node* node);
109
110  // If the node is coupled, returns the coupled control edge index.
111  inline base::Optional<int> GetCoupledControlEdge(Node* node);
112  void IncrementUnscheduledUseCount(Node* node, Node* from);
113  void DecrementUnscheduledUseCount(Node* node, Node* from);
114
115  static void PropagateImmediateDominators(BasicBlock* block);
116
117  // Uses {common_dominator_cache_} to speed up repeated calls.
118  BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2);
119  // Returns the common dominator of {b1} and {b2} if it can be found in
120  // {common_dominator_cache_}, or nullptr otherwise.
121  // Not meant to be called directly, only from {GetCommonDominator}.
122  BasicBlock* GetCommonDominatorIfCached(BasicBlock* b1, BasicBlock* b2);
123
124  // Phase 1: Build control-flow graph.
125  friend class CFGBuilder;
126  void BuildCFG();
127
128  // Phase 2: Compute special RPO and dominator tree.
129  friend class SpecialRPONumberer;
130  void ComputeSpecialRPONumbering();
131  void GenerateDominatorTree();
132
133  // Phase 3: Prepare use counts for nodes.
134  friend class PrepareUsesVisitor;
135  void PrepareUses();
136
137  // Phase 4: Schedule nodes early.
138  friend class ScheduleEarlyNodeVisitor;
139  void ScheduleEarly();
140
141  // Phase 5: Schedule nodes late.
142  friend class ScheduleLateNodeVisitor;
143  void ScheduleLate();
144
145  // Phase 6: Seal the final schedule.
146  void SealFinalSchedule();
147
148  void FuseFloatingControl(BasicBlock* block, Node* node);
149  void MovePlannedNodes(BasicBlock* from, BasicBlock* to);
150};
151
152
153DEFINE_OPERATORS_FOR_FLAGS(Scheduler::Flags)
154
155}  // namespace compiler
156}  // namespace internal
157}  // namespace v8
158
159#endif  // V8_COMPILER_SCHEDULER_H_
160