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