Line data Source code
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 : 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 9 : 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 10549045 : int ToInt() const { return static_cast<int>(index_); }
49 20851306 : size_t ToSize() const { return index_; }
50 : static Id FromSize(size_t index) { return Id(index); }
51 20848121 : 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 7 : BasicBlockVector& predecessors() { return predecessors_; }
72 : const BasicBlockVector& predecessors() const { return predecessors_; }
73 : size_t PredecessorCount() const { return predecessors_.size(); }
74 30951815 : BasicBlock* PredecessorAt(size_t index) { return predecessors_[index]; }
75 : void ClearPredecessors() { predecessors_.clear(); }
76 : void AddPredecessor(BasicBlock* predecessor);
77 :
78 : // Successors.
79 6 : BasicBlockVector& successors() { return successors_; }
80 : const BasicBlockVector& successors() const { return successors_; }
81 : size_t SuccessorCount() const { return successors_.size(); }
82 63748317 : 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 : using value_type = Node*;
88 : bool empty() const { return nodes_.empty(); }
89 : size_t size() const { return nodes_.size(); }
90 93189886 : 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 : using iterator = NodeVector::iterator;
97 : iterator begin() { return nodes_.begin(); }
98 : iterator end() { return nodes_.end(); }
99 :
100 3966808 : void RemoveNode(iterator it) { nodes_.erase(it); }
101 :
102 : using const_iterator = NodeVector::const_iterator;
103 : const_iterator begin() const { return nodes_.begin(); }
104 : const_iterator end() const { return nodes_.end(); }
105 :
106 : using reverse_iterator = NodeVector::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 48 : 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 27660277 : void set_deferred(bool deferred) { deferred_ = deferred; }
126 :
127 : int32_t dominator_depth() const { return dominator_depth_; }
128 27086797 : void set_dominator_depth(int32_t depth) { dominator_depth_ = depth; }
129 :
130 : BasicBlock* dominator() const { return dominator_; }
131 24218639 : void set_dominator(BasicBlock* dominator) { dominator_ = dominator; }
132 :
133 : BasicBlock* rpo_next() const { return rpo_next_; }
134 40568556 : 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 272485 : 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 226 : 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 2159 : return AddSuccessor(block, succ);
258 : }
259 :
260 0 : const BasicBlockVector* all_blocks() const { return &all_blocks_; }
261 249018 : BasicBlockVector* rpo_order() { return &rpo_order_; }
262 28 : 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_
|
