V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
schedule.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_SCHEDULE_H_
6 #define V8_COMPILER_SCHEDULE_H_
7 
8 #include <iosfwd>
9 
10 #include "src/base/compiler-specific.h"
11 #include "src/globals.h"
12 #include "src/zone/zone-containers.h"
13 
14 namespace v8 {
15 namespace internal {
16 namespace compiler {
17 
18 // Forward declarations.
19 class BasicBlock;
20 class BasicBlockInstrumentor;
21 class Node;
22 
23 typedef ZoneVector<BasicBlock*> BasicBlockVector;
24 typedef ZoneVector<Node*> NodeVector;
25 
26 // A basic block contains an ordered list of nodes and ends with a control
27 // node. Note that if a basic block has phis, then all phis must appear as the
28 // first nodes in the block.
29 class V8_EXPORT_PRIVATE BasicBlock final
30  : public NON_EXPORTED_BASE(ZoneObject) {
31  public:
32  // Possible control nodes that can end a block.
33  enum Control {
34  kNone, // Control not initialized yet.
35  kGoto, // Goto a single successor block.
36  kCall, // Call with continuation as first successor, exception
37  // second.
38  kBranch, // Branch if true to first successor, otherwise second.
39  kSwitch, // Table dispatch to one of the successor blocks.
40  kDeoptimize, // Return a value from this method.
41  kTailCall, // Tail call another method from this method.
42  kReturn, // Return a value from this method.
43  kThrow // Throw an exception.
44  };
45 
46  class Id {
47  public:
48  int ToInt() const { return static_cast<int>(index_); }
49  size_t ToSize() const { return index_; }
50  static Id FromSize(size_t index) { return Id(index); }
51  static Id FromInt(int index) { return Id(static_cast<size_t>(index)); }
52 
53  private:
54  explicit Id(size_t index) : index_(index) {}
55  size_t index_;
56  };
57 
58  BasicBlock(Zone* zone, Id id);
59 
60  Id id() const { return id_; }
61 #if DEBUG
62  void set_debug_info(AssemblerDebugInfo debug_info) {
63  debug_info_ = debug_info;
64  }
65  AssemblerDebugInfo debug_info() const { return debug_info_; }
66 #endif // DEBUG
67 
68  void Print();
69 
70  // Predecessors.
71  BasicBlockVector& predecessors() { return predecessors_; }
72  const BasicBlockVector& predecessors() const { return predecessors_; }
73  size_t PredecessorCount() const { return predecessors_.size(); }
74  BasicBlock* PredecessorAt(size_t index) { return predecessors_[index]; }
75  void ClearPredecessors() { predecessors_.clear(); }
76  void AddPredecessor(BasicBlock* predecessor);
77 
78  // Successors.
79  BasicBlockVector& successors() { return successors_; }
80  const BasicBlockVector& successors() const { return successors_; }
81  size_t SuccessorCount() const { return successors_.size(); }
82  BasicBlock* SuccessorAt(size_t index) { return successors_[index]; }
83  void ClearSuccessors() { successors_.clear(); }
84  void AddSuccessor(BasicBlock* successor);
85 
86  // Nodes in the basic block.
87  typedef Node* value_type;
88  bool empty() const { return nodes_.empty(); }
89  size_t size() const { return nodes_.size(); }
90  Node* NodeAt(size_t index) { return nodes_[index]; }
91  size_t NodeCount() const { return nodes_.size(); }
92 
93  value_type& front() { return nodes_.front(); }
94  value_type const& front() const { return nodes_.front(); }
95 
96  typedef NodeVector::iterator iterator;
97  iterator begin() { return nodes_.begin(); }
98  iterator end() { return nodes_.end(); }
99 
100  void RemoveNode(iterator it) { nodes_.erase(it); }
101 
102  typedef NodeVector::const_iterator const_iterator;
103  const_iterator begin() const { return nodes_.begin(); }
104  const_iterator end() const { return nodes_.end(); }
105 
106  typedef NodeVector::reverse_iterator reverse_iterator;
107  reverse_iterator rbegin() { return nodes_.rbegin(); }
108  reverse_iterator rend() { return nodes_.rend(); }
109 
110  void AddNode(Node* node);
111  template <class InputIterator>
112  void InsertNodes(iterator insertion_point, InputIterator insertion_start,
113  InputIterator insertion_end) {
114  nodes_.insert(insertion_point, insertion_start, insertion_end);
115  }
116 
117  // Accessors.
118  Control control() const { return control_; }
119  void set_control(Control control);
120 
121  Node* control_input() const { return control_input_; }
122  void set_control_input(Node* control_input);
123 
124  bool deferred() const { return deferred_; }
125  void set_deferred(bool deferred) { deferred_ = deferred; }
126 
127  int32_t dominator_depth() const { return dominator_depth_; }
128  void set_dominator_depth(int32_t depth) { dominator_depth_ = depth; }
129 
130  BasicBlock* dominator() const { return dominator_; }
131  void set_dominator(BasicBlock* dominator) { dominator_ = dominator; }
132 
133  BasicBlock* rpo_next() const { return rpo_next_; }
134  void set_rpo_next(BasicBlock* rpo_next) { rpo_next_ = rpo_next; }
135 
136  BasicBlock* loop_header() const { return loop_header_; }
137  void set_loop_header(BasicBlock* loop_header);
138 
139  BasicBlock* loop_end() const { return loop_end_; }
140  void set_loop_end(BasicBlock* loop_end);
141 
142  int32_t loop_depth() const { return loop_depth_; }
143  void set_loop_depth(int32_t loop_depth);
144 
145  int32_t loop_number() const { return loop_number_; }
146  void set_loop_number(int32_t loop_number) { loop_number_ = loop_number; }
147 
148  int32_t rpo_number() const { return rpo_number_; }
149  void set_rpo_number(int32_t rpo_number);
150 
151  // Loop membership helpers.
152  inline bool IsLoopHeader() const { return loop_end_ != nullptr; }
153  bool LoopContains(BasicBlock* block) const;
154 
155  // Computes the immediate common dominator of {b1} and {b2}. The worst time
156  // complexity is O(N) where N is the height of the dominator tree.
157  static BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2);
158 
159  private:
160  int32_t loop_number_; // loop number of the block.
161  int32_t rpo_number_; // special RPO number of the block.
162  bool deferred_; // true if the block contains deferred code.
163  int32_t dominator_depth_; // Depth within the dominator tree.
164  BasicBlock* dominator_; // Immediate dominator of the block.
165  BasicBlock* rpo_next_; // Link to next block in special RPO order.
166  BasicBlock* loop_header_; // Pointer to dominating loop header basic block,
167  // nullptr if none. For loop headers, this points to
168  // enclosing loop header.
169  BasicBlock* loop_end_; // end of the loop, if this block is a loop header.
170  int32_t loop_depth_; // loop nesting, 0 is top-level
171 
172  Control control_; // Control at the end of the block.
173  Node* control_input_; // Input value for control.
174  NodeVector nodes_; // nodes of this block in forward order.
175 
176  BasicBlockVector successors_;
177  BasicBlockVector predecessors_;
178 #if DEBUG
179  AssemblerDebugInfo debug_info_;
180 #endif
181  Id id_;
182 
183  DISALLOW_COPY_AND_ASSIGN(BasicBlock);
184 };
185 
186 std::ostream& operator<<(std::ostream&, const BasicBlock&);
187 std::ostream& operator<<(std::ostream&, const BasicBlock::Control&);
188 std::ostream& operator<<(std::ostream&, const BasicBlock::Id&);
189 
190 // A schedule represents the result of assigning nodes to basic blocks
191 // and ordering them within basic blocks. Prior to computing a schedule,
192 // a graph has no notion of control flow ordering other than that induced
193 // by the graph's dependencies. A schedule is required to generate code.
194 class V8_EXPORT_PRIVATE Schedule final : public NON_EXPORTED_BASE(ZoneObject) {
195  public:
196  explicit Schedule(Zone* zone, size_t node_count_hint = 0);
197 
198  // Return the block which contains {node}, if any.
199  BasicBlock* block(Node* node) const;
200 
201  bool IsScheduled(Node* node);
202  BasicBlock* GetBlockById(BasicBlock::Id block_id);
203 
204  size_t BasicBlockCount() const { return all_blocks_.size(); }
205  size_t RpoBlockCount() const { return rpo_order_.size(); }
206 
207  // Check if nodes {a} and {b} are in the same block.
208  bool SameBasicBlock(Node* a, Node* b) const;
209 
210  // BasicBlock building: create a new block.
211  BasicBlock* NewBasicBlock();
212 
213  // BasicBlock building: records that a node will later be added to a block but
214  // doesn't actually add the node to the block.
215  void PlanNode(BasicBlock* block, Node* node);
216 
217  // BasicBlock building: add a node to the end of the block.
218  void AddNode(BasicBlock* block, Node* node);
219 
220  // BasicBlock building: add a goto to the end of {block}.
221  void AddGoto(BasicBlock* block, BasicBlock* succ);
222 
223  // BasicBlock building: add a call at the end of {block}.
224  void AddCall(BasicBlock* block, Node* call, BasicBlock* success_block,
225  BasicBlock* exception_block);
226 
227  // BasicBlock building: add a branch at the end of {block}.
228  void AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
229  BasicBlock* fblock);
230 
231  // BasicBlock building: add a switch at the end of {block}.
232  void AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks,
233  size_t succ_count);
234 
235  // BasicBlock building: add a deoptimize at the end of {block}.
236  void AddDeoptimize(BasicBlock* block, Node* input);
237 
238  // BasicBlock building: add a tailcall at the end of {block}.
239  void AddTailCall(BasicBlock* block, Node* input);
240 
241  // BasicBlock building: add a return at the end of {block}.
242  void AddReturn(BasicBlock* block, Node* input);
243 
244  // BasicBlock building: add a throw at the end of {block}.
245  void AddThrow(BasicBlock* block, Node* input);
246 
247  // BasicBlock mutation: insert a branch into the end of {block}.
248  void InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
249  BasicBlock* tblock, BasicBlock* fblock);
250 
251  // BasicBlock mutation: insert a switch into the end of {block}.
252  void InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw,
253  BasicBlock** succ_blocks, size_t succ_count);
254 
255  // Exposed publicly for testing only.
256  void AddSuccessorForTesting(BasicBlock* block, BasicBlock* succ) {
257  return AddSuccessor(block, succ);
258  }
259 
260  const BasicBlockVector* all_blocks() const { return &all_blocks_; }
261  BasicBlockVector* rpo_order() { return &rpo_order_; }
262  const BasicBlockVector* rpo_order() const { return &rpo_order_; }
263 
264  BasicBlock* start() { return start_; }
265  BasicBlock* end() { return end_; }
266 
267  Zone* zone() const { return zone_; }
268 
269  private:
270  friend class Scheduler;
271  friend class BasicBlockInstrumentor;
272  friend class RawMachineAssembler;
273 
274  // For CSA/Torque: Ensure properties of the CFG assumed by further stages.
275  void EnsureCFGWellFormedness();
276  // For CSA/Torque: Eliminates unnecessary phi nodes, including phis with a
277  // single input. The latter is necessary to ensure the property required for
278  // SSA deconstruction that the target block of a control flow split has no
279  // phis.
280  void EliminateRedundantPhiNodes();
281  // Ensure split-edge form for a hand-assembled schedule.
282  void EnsureSplitEdgeForm(BasicBlock* block);
283  // Ensure entry into a deferred block happens from a single hot block.
284  void EnsureDeferredCodeSingleEntryPoint(BasicBlock* block);
285  // Move Phi operands to newly created merger blocks
286  void MovePhis(BasicBlock* from, BasicBlock* to);
287  // Copy deferred block markers down as far as possible
288  void PropagateDeferredMark();
289 
290  void AddSuccessor(BasicBlock* block, BasicBlock* succ);
291  void MoveSuccessors(BasicBlock* from, BasicBlock* to);
292 
293  void SetControlInput(BasicBlock* block, Node* node);
294  void SetBlockForNode(BasicBlock* block, Node* node);
295 
296  Zone* zone_;
297  BasicBlockVector all_blocks_; // All basic blocks in the schedule.
298  BasicBlockVector nodeid_to_block_; // Map from node to containing block.
299  BasicBlockVector rpo_order_; // Reverse-post-order block list.
300  BasicBlock* start_;
301  BasicBlock* end_;
302 
303  DISALLOW_COPY_AND_ASSIGN(Schedule);
304 };
305 
306 V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream&, const Schedule&);
307 
308 } // namespace compiler
309 } // namespace internal
310 } // namespace v8
311 
312 #endif // V8_COMPILER_SCHEDULE_H_
Definition: libplatform.h:13