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